精华内容
下载资源
问答
  • 矩阵快速幂
    2021-06-01 19:59:06

    前言

    如果你对这篇文章可感兴趣,可以点击「【访客必读 - 指引页】一文囊括主页内所有高质量博客」,查看完整博客分类与对应链接。

    设想这样一个场景,面试官给了你一道算法题,你很快确定这是一道递推问题,并给出了 O(n) 的解题方法,然而面试官却继续问:“还能继续优化吗?”

    这样类似的场景并不少见,因为算法不仅追求「正确」,还追求「效率」,而这也正是优化方法的意义。

    本文即将介绍的「矩阵快速幂」便是一种常见的优化递推的方法,能将 O(n) 的递推过程加速至 O(log(n)),使效率显著提升。

    矩阵运算

    首先我们回顾一下「矩阵」,一个 n * m 的矩阵可以看作是一个 n * m 的二维数组,而矩阵的加减法就是将两个矩阵对应位置上的数相加减,即 C = A + B 意味着矩阵 C 中任意一点 C i , j = A i

    更多相关内容
  • 矩阵快速幂

    2018-05-21 10:44:48
    PPT中简单讲解了一下矩阵的基础,以及矩阵快速幂的写法和简单应用,练习题网上有很多
  • 矩阵快速幂算法

    2022-03-10 08:59:27
    矩阵快速幂算法、利用矩阵快速幂计算斐波那契数列 矩阵快速幂的本质就是 矩阵+快速幂,思路没什么变化。 快速幂的思路见之前的 快速幂介绍,这里就不多说了。 至于矩阵的话,知道矩阵是啥,怎么算乘法就可以了。 ...

    矩阵快速幂算法

    矩阵快速幂的本质就是 矩阵+快速幂,思路没什么变化。
    快速幂的思路见之前的 快速幂介绍,这里就不多说了。
    至于矩阵的话,知道矩阵是啥,怎么算乘法就可以了。

    相关矩阵基础

    注:已经了解矩阵的可以跳过本部分内容。

    简单来说 n ∗ m n*m nm 的矩阵就是个 n n n m m m 列 的大方块。
    矩阵要进行乘法运算必须保证第一个矩阵的列数=第二个矩阵的行数。
    也就是说 n 1 ∗ m 1 n_1 * m_1 n1m1 的矩阵 a 与 n 2 ∗ m 2 n_2 * m_2 n2m2 的矩阵 b 相乘,需要保证 m 1 = n 2 m_1=n_2 m1=n2 最终得到的结果为 n 1 ∗ m 2 n_1*m_2 n1m2 的矩阵 c。
    对于得到的矩阵 c ,它每个位置的结果为第一个矩阵的第 i i i 行 与第二个矩阵的第 j j j 列相乘求和得到。
    即结果矩阵中 i i i j j j 列的元素 c [ i ] [ j ] = ∑ k = 1 m 1 a [ i ] [ k ] ∗ b [ k ] [ j ] c[i][j]=\sum_{k=1}^{m_1}a[i][k]*b[k][j] c[i][j]=k=1m1a[i][k]b[k][j]

    具体例子:

    [ 1 2 ] ∗ [ 1 2 3 4 ] = [ 1 ∗ 1 + 2 ∗ 3 1 ∗ 2 + 2 ∗ 4 ] = [ 7 6 ] \begin{bmatrix} 1 & 2 \end{bmatrix}* \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}= \begin{bmatrix} 1*1+2*3 & 1*2+2*4 \end{bmatrix}= \begin{bmatrix} 7 & 6 \end{bmatrix} [12][1324]=[11+2312+24]=[76]

    矩阵快速幂

    只需要在原来快速幂的基础上,把数字换成矩阵即可。
    以下为原版整数的快速幂:

    #include <bits/stdc++.h>
    using namespace std;
    
    int main()
    {
    	long long a,b,c,ans;
    	while(cin>>a>>b>>c)
    	{
    		ans=1;
    		while(b>0)
    		{
    			if(b&1)ans=ans*a%c;
    			a=a*a%c;
    			b>>=1;
    		}
    		cout<<ans<<endl;
    	}
    	return 0;
    }
    
    

    代码以洛谷 P3390 模板题为例,关键部分在 qpow 函数中。
    为保证原有结构尽可能不被修改,矩阵快速幂代码矩阵乘法部分放在重载运算符中。
    Matrix::unit 为单位矩阵,这里在读入数据时顺便初始化了,也可以在 qpow 中进行初始化。

    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll; 
    
    ll n,k,mod=1e9+7;
    class Matrix
    {
    public:
    	static Matrix unit;
    	ll data[100][100];
    	int n,m;
    	
    	Matrix operator *(Matrix &mat)
    	{
    		Matrix tmp=Matrix::unit;
    		tmp.n=this->n;
    		tmp.m=mat.m;
    		for(int i=0;i<this->n;i++)
    		{
    			for(int j=0;j<mat.m;j++)
    			{
    				tmp.data[i][j] = 0;
    				for(int k=0;k<this->m;k++)
    				{
    					tmp.data[i][j] += this->data[i][k]*mat.data[k][j];
    					tmp.data[i][j] %= mod;
    				}
    			}
    		}
    		return tmp;
    	}
    	
    	void print()
    	{
    		for(int i=0;i<n;i++)
    		{
    			for(int j=0;j<m;j++)
    			{
    				if(j!=0)cout<<" ";
    				cout<<this->data[i][j];
    			}
    			cout<<"\n";
    		}
    	}
    };
    
    Matrix Matrix::unit;
    Matrix mat;
    
    Matrix qpow(Matrix m1,ll b,ll mod)
    {
    	Matrix ans=Matrix::unit;
    	while(b>0)
    	{
    		if(b&1)ans=ans*m1;
    		m1=m1*m1;
    		b>>=1;
    	}
    	return ans;
    }
    
    int main()
    {
    	cin>>n>>k;
    	mat.n=mat.m=n;
    	Matrix::unit.n=Matrix::unit.m=n;
    	for(int i=0;i<n;i++)
    	{
    		for(int j=0;j<n;j++)
    		{
    			cin>>mat.data[i][j];
    		}
    		Matrix::unit.data[i][i]=1;
    	}
    	mat=qpow(mat,k,mod);
    	mat.print();
    	return 0;
    }
    
    

    补充说明:
    如果题目涉及多次取模,建议将矩阵乘法写成 Matrix 的成员函数或者单独一个乘法函数。

    应用:快速计算斐波那契数列

    斐波那契数列定义:F(0)=0,F(1)=1, F(n)=F(n - 1)+F(n - 2)(n ≥ 2,n ∈ N*)
    如果需要求的 n 值很大,可能会在递推时超时 ,此时可以利用矩阵快速幂求解。
    首先将递推式构造成矩阵形式:
    [ F ( n ) F ( n − 1 ) ] = [ 1 1 1 0 ] ∗ [ F ( n − 1 ) F ( n − 2 ) ] \begin{bmatrix} F(n) \\ F(n-1) \end{bmatrix}= \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}* \begin{bmatrix} F(n-1) \\ F(n-2) \end{bmatrix} [F(n)F(n1)]=[1110][F(n1)F(n2)]
    这样计算数列的第 n 项时可以利用中间矩阵的 n-1 次幂乘上数列的前两项:
    [ F ( n ) F ( n − 1 ) ] = [ 1 1 1 0 ] n − 1 ∗ [ F ( 1 ) F ( 0 ) ] \begin{bmatrix} F(n) \\ F(n-1) \end{bmatrix}= \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{n-1}* \begin{bmatrix} F(1) \\ F(0) \end{bmatrix} [F(n)F(n1)]=[1110]n1[F(1)F(0)]
    因为 F(0)=0 F(1)=1,所以只需要快速计算中间的矩阵,矩阵的第一行第一列位置就是要计算的 F(n)。
    由于快速幂文章中介绍的模运算性质,如果题目需要计算时需要对斐波那契数列取模,那么可以直接在矩阵运算过程中进行取模。
    题目可以参考 NEFU OJ 2348 小蓝与斐波拉契数列

    展开全文
  • c++ 矩阵快速幂封装支持矩阵乘法取模等
  • 目录1、幂是什么2、普通幂方法一方法二3、快速幂核心思想快速幂过程快速幂位运算样例代码数据解析取余运算练习题4、矩阵快速幂矩阵乘法快速幂和矩阵乘法有什么关联? 1、幂是什么 当 m 为正整数 , nᵐ 表示 m 个...


    1、幂是什么

    • 当 m 为正整数 , nᵐ 表示 m 个 n 相乘 ;

    • 把nᵐ看作乘方的结果,叫做n的m次幂,也叫n的m次方

    • nᵐ 把看作乘方的结果,叫做的次幂。

    • nᵐ 中 , n 是底数 , m是指数

    • … … 这一段是拿来水行数的,能不看就不看…

      具体更多内容 , 大家可以使用 百度优先搜索 学习 。

      给大家附上快速通道


    2、普通幂

    对于普通幂这种东西,当今基本上很少用的,因为已经有比普通求幂更好的方法了——快速幂。

    • 普通求幂 :时间复杂度为 O( n )

    方法一

    自带函数 pow (需要调用 < cmath > 或 < math.h > 库)**

    pow(_Tp __x, _Up __y)
    {
        	typedef typename __gnu_cxx::__promote_2<_Tp, _Up>::__type __type;
        	return pow(__type(__x), __type(__y));
    }
    

    pow( x , y ) 表示 y 的 x 次方,也表示 y 的 x 次幂

    方法二

    手写代码

    int x , y , ans = 1; // x 表示 底数 , y 表示 指数 , ans 表示结果
    for(int i = 1 ; i <= y ; i ++)
    	ans *= x ;
    

    当然,如果不是为了节省时间的话,能用 pow 更好,因为方便快捷


    3、快速幂

    核心思想

    快速幂的核心思想:

    • 每一步把指数分成两半

    • 相应的底数做平方运算

    这样做可以使得:

    • 非常大的 指数不断变小

    • 需要执行的 循环次数 也变小

    然而计算结果不变

    最终 时间复杂度 为 O( log₂ n )


    快速幂过程

    过程即如下图所示

    210 = 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2

    210 = (2 * 2) * (2 * 2) * (2 * 2) * (2 * 2) * (2 * 2)

    210 = ( (2 * 2) * (2 * 2) ) * ( (2 * 2) * (2 * 2) ) * (2 * 2)

    210 = 162 * 41

    即相当于将 乘号 减少 使得循环减少 来达成 时间减少


    快速幂位运算

    为了使得 快速幂 获得 更快 的时间,我们一般使用 位运算

    快速幂需要使用的位运算符有以下两个

    • b & 1

    取 b 在 二进制 状态下的 最低位 ,判断是否 等于1,为真则返回1,为假则返回0,一般用于判断奇偶,时间比普通的 " b % 2 == 1 "要快。

    • b >>= 1

    把 b 在 二进制 的状态下向 右移一位 ,即去掉其二进制位的 最低位 ,其相当于 " b /= 2 ",同上,前者会比后者要快。

    例如 b = 9 , 9 的二进制是 (1001)₂ ,则 b >>= 1 相当于把 (1001)₂ 向右移一位,变成 (100)₂ , 则 (100)₂ 为 4,即 ⌊9 / 2⌋ = 4。


    样例代码

    long long mi(long long a,long long b) // a 表示 底数 b 表示 指数
    {
        ans = 1; // ans 表示 答案
        while( b ) //当 b 不为 0 时
        {
            if(b&1) //当 b 为 奇数时 
                ans *= a;
            a *= a;
            b>>=1; //b 除 2
        }
        return ans;
    }
    

    数据解析

    相信 你们(指 初学快速幂 的人)那么容易 就看懂 就学懂 !!!

    我这只 蒟蒻 也在这算法上模拟了半天才懂 !!

    最简单的办法——上数据!!!

    当 mi( 2 , 10 ) 时,让我们康康数据

    ans = 1

    while : b > 0 进入循环
    if : b & 1 = 0 不保存乘积
    ans = 1
    a *= a : a = 2 * 2
    a = 4
    b >>= 1 : b = 10 >> 1
    b = 5

    while : b > 0 继续循环
    if : b & 1 = 1 保存乘积
    ans = 4 (在这里,我们就把 210 改成 ( 2 * 2 )5 了)
    a *= a : a = 4 * 4
    a = 16
    b >>= 1 : b = 5 >> 1
    b = 2

    while : b > 0 继续循环
    if : b & 1 = 0 不保存乘积
    ans = 4
    a *= a : a = 16 * 16
    a = 256
    b >>= 1 : b = 2 >> 1
    b = 1

    while : b > 0 继续循环
    if : b & 1 = 1 保存乘积
    ans = 1024 (在这里,我们就把 (2 * 2)5 改成 ( 2 * 2 * 2 * 2 )2 * ( 2 * 2 )1 了)
    a *= a : a = 256 * 256
    a = (我不算了)
    b >>= 1 : b = 1 >> 1
    b = 0

    while : b = 0 退出循环
    return ans

    因此得到 mi( 2 , 10 ) = 1024

    你是不是感觉,啊,这样子更麻烦啊,耗费的时间不是更多吗!!

    实际上,等数据大一些后,快速幂便能展现它的优势了

    至于为什么,大家可以使用 百度优先搜索 (因为我也不想说了)

    如果还是不懂为什么 b 要除以 2 ,a 要平方 ,请看:

    ab 举个例子 24 是不是 等于 ( 2 * 2 )2

    a 是不是平方了? b 是不是 除以2了?快速幂就是这样子压缩的…


    取余运算

    这东西不用教都会,直接在乘的地方模就行了

    long long mi(long long a,long long b) // a 表示 底数 b 表示 指数
    {
        ans = 1; // ans 表示 答案
        while( b ) //当 b 不为 0 时
        {
            if(b&1) //当 b 为 奇数时 
                ans = ( a * ans ) % mod;
            a *= a;
            b>>=1; //b 除 2
        }
        return ans;
    }
    

    模这个东西又引出来一个问题,那么数据太大怎么办??

    待会在高精度快速幂便会讲


    练习题

    我来给 洛谷 打广告了!!!

    >>快速幂、取余运算<<

    好吧,我没找到其他题,就一道模板题


    4、矩阵快速幂

    矩阵乘法

    了解矩阵快速幂之前,建议大家可以去网上找找关于矩阵乘法的帖子学习,尽可能的看懂,因为 我不能保证我讲的人人都看得懂…

    在这里插入图片描述
    如上图(是不是好丑)即为例子

    矩阵乘法相乘方式 和普通乘法不同

    在这里插入图片描述
    这两个圈起来的方框是不是有一个 相同点(1,1) ,这个点就是是我们要保存的数据的点
    在这里插入图片描述
    那么,我们怎么算这个值呢?

    看到被蓝圈圈起来这两个数了吗(此时和我同机房的XX说没看见)?

    我们把这两个数乘起来
    在这里插入图片描述
    再继续把这个框内的另外两个数圈起来相乘

    得到下图:
    在这里插入图片描述
    还没看出规律吗??

    矩阵C

    C(1,1) C(1,2)
    C(2,1) C(2,2)

    矩阵D

    D(1,1) D(1,2)
    D(2,1) D(2,2)

    假设 i 表示 第几行 , j 表示 第几列 , 矩阵C * 矩阵D = 矩阵E

    则可以得到 :

    E( i , j ) =
    C( i , 1 ) * D( 1 , j ) +
    C( i , 2 ) * D( 2 , j ) + … +
    C( i , n ) * D( n , j )

    再不懂,我也没办法了,尽力了…


    快速幂和矩阵乘法有什么关联?

    有时候你做题会遇到这样一句话: 给你一个 矩阵A ,如果 矩阵B = Ak ,请求出 矩阵B

    矩阵乘法 + 快速幂 = 矩阵快速幂 (因为都是同级运算,因此可以拼合)

    知道矩阵乘法以后,可能都会想着暴力算。实际上,矩阵快速幂 会比 暴力运算 快很多!

    这样子就解答了我们前面的这个问题:

    图片
    因为 —— 要乘的变多了!


    矩阵快速幂在快速幂的基础上改了什么?

    矩阵快速幂模板如下,康康改了什么

    node power( node a , node b , int n ) //矩阵乘法
    {
        node c;
        for(int i = 1;i <= n;i ++)
            for(int l = 1;l <= n;l ++)
    		{
                c.map[i][l] = 0;
                for(int j = 1;j <= n;j ++)
                    c.map[i][l] += (a.map[i][j] * b.map[j][l]) % mo;
                c.map[i][l] %= mo;
            }
        return c;
    }
    
    node power2( node a , int b , int n ) 
    {
        node sum;
        memset(sum.map,0,sizeof(sum.map));
        for(int i = 1;i <= 10;i ++) sum.map[i][i] = 1; //初始化
        while(b>0)
        {
            if(b & 1) sum = power(sum,a,n);
            b >>= 1;
            a = power(a,a,n);
        }
        return sum;
    }
    

    备注:这是我初学矩阵乘法时的代码,有点水

    实际上也就多了一个 矩阵乘法 而已

    而改的只有…

    if(b & 1) sum = power(sum,a,n);
    b >>= 1;
    a = power(a,a,n);

    其实矩阵快速幂就是把矩阵乘法每一次相乘看作一个整体,用一个函数来实现更改值

    简单来说就是把 快速幂运算中每一次保存的值 换成 每一次保存的矩阵


    练习题

    我又来给 洛谷 打广告了! <<模板题

    其他题

    POJ3233

    HDU5015

    HUD2276

    POJ3070

    至于答案使用 百度优先搜索 就得了


    矩阵乘法(快速幂)后言

    对于矩阵乘法(包括快速幂),应用率也比较高的了,甚至连斐波那契数也可以算。不过好东西也是有缺点的,时间复杂度高达O( n3 )甚至不止这么少,如果数据太大的话,要注意常数优化,就连板题也要注意


    5、高精度快速幂

    高精度快速幂 顾名思义 就是 高精度乘法 + 快速幂

    没了,就这么多…


    那么高精度乘法…不会打的,推荐你使用…百度优先搜索 学习,学完后再来看我这,避免我带偏

    感觉还行的快速通道


    实际上,高精度乘法和矩阵乘法一样,只需要把 普通快速幂 相乘的地方 给 替换 成 高精度乘法 就行了

    此处三篇代码还在修改中,请勿使用某两个快捷键

    void mi(int b)
    {
    	while(b)
    	{
    		if(b & 1) mul_ans_and_a(); //保存乘积,ans和a高精度相乘
    		
    		b >>= 1;
    		
    		mul_a_and_a(); //取平方函数 
    	}
    } 
    

    和矩阵乘法是不是感觉很像?? (此时和我同机房的XX说不像)


    void mul_ans_and_a()
    {
    	/*
    	全局变量:
    	
    		(int) n  存储了需要保留的位数
    		
    		(int) ans[1000] 存储了答案
    		
    		(int) a[1000] 存储了底数 
    		
    	*/
    	int cnt[1000];
    	
        memset(cnt,0,sizeof(cnt)); //初始化清空 
        
        for(int i = 1;i <= n;i ++) //高精度乘积计算 
        
            for(int j = 1;j <= n;j ++)
            
            	cnt[i + j - 1] += ans[i] * a[j];
        
        for(int i = 1;i < n;i ++)
        
            if(cnt[i] >= 10)
            
            	cnt[i + 1] += cnt[i] / 10,
            	
            	cnt[i] %= 10;
            	
        memcpy(ans,cnt,sizeof(ans)); //复制数组 
    }
    

    memcpy复制函数快速通道

    void mul_a_and_a()
    {
    	/*
    	全局变量:
    	
    		(int) n  存储了需要保留的位数
    		
    		(int) a[1000] 存储了底数 
    		
    	*/
    	int cnt[1000];
    	
        memset(cnt,0,sizeof(cnt)); //初始化清空 
        
        for(int i = 1;i <= n;i ++) //高精度乘积计算 
        
            for(int j = 1;j <= n;j ++)
            
            	cnt[i + j - 1] += a[i] * a[j];
        
        for(int i = 1;i < 505;i ++)
        
            if(cnt[i] >= 10)
            
            	cnt[i + 1] += cnt[i] / 10,
            	
            	cnt[i] %= 10;
            	
        memcpy(ans,a,sizeof(ans)); //复制数组 
    }
    
    

    几乎一样,改几个代码罢了


    练习题

    *我又来给 洛谷 打广告了! <<模板题


    结言

    我不知道你会不会把 快速幂 想的太复杂,但是事实证明——只要你练的多了,你就熟了。快速幂我不知道还有没有其他专题,反正吧,快速幂是一个特别有用的东西,也许考的不多,但是你要相信一件事:快速幂要么考的很深(几乎看不出来那种),要不就 明摆模板题(数据给你出的很大的题),只有真正学会了,会用了,才会优化,优化什么?这就要看题目性质了!


    该帖子基本信息

    字数 : XXXX
    行数 : XXX
    完成耗时 : 约 6 个小时


    作者留言

    麻烦各位如果发现错误、用词、语不当等,可在评论区写下您的意见和看法,谢谢!

    展开全文
  • 矩阵快速幂其实是一个用于加速计算的一个算法。 矩阵快速幂和我们普通的数的快速幂是没有啥太大的区别的。不过一个是数,一个是矩阵。 矩阵快速幂的应用: 矩阵加速递推。例如:如果有一道题目让你求斐波那契数列第n...

    矩阵快速幂其实是一个用于加速计算的一个算法。

    矩阵快速幂和我们普通的数的快速幂是没有啥太大的区别的。不过一个是数,一个是矩阵。
    矩阵快速幂的应用: 矩阵加速递推。例如:如果有一道题目让你求斐波那契数列第n项的值,最简单的方法莫过于直接递推了。但是如果n的范围达到了 1018级别,递推就不行了,稳 TLE。考虑矩阵加速递推。

    看一个模板题来了解矩阵快速幂:
    在这里插入图片描述

    #include<bits/stdc++.h>
    using namespace std;
    const int N=110;
    const int mod=1e9+7;
    typedef long long int LL;
    LL n,m;
    struct node{LL a[N][N];}a,ans;
    node mul(node a,node b,int p)
    {
    	node sum={0};
    	for(int i=1;i<=n;i++)
    		for(int k=1;k<=n;k++)
    			for(int j=1;j<=n;j++)
    				sum.a[i][j]=(sum.a[i][j]+a.a[i][k]*b.a[k][j])%p;
    	return sum;
    }
    node  qsm(node a,LL b,LL p)
    {
    	node sum={0};
    	for(int i=1;i<=n;i++) sum.a[i][i]=1;//单元矩阵
    	while(b) 
    	{
    		if(b&1) sum=mul(sum,a,mod);
    		b>>=1;
    		a=mul(a,a,mod);
    	}
    	return sum;
    }
    int main(void)
    {
    	cin>>n>>m;
    	for(int i=1;i<=n;i++)
    		for(int j=1;j<=n;j++) cin>>a.a[i][j];
    	ans=qsm(a,m,mod);
    	for(int i=1;i<=n;i++)
    	{
    		for(int j=1;j<=n;j++) cout<<ans.a[i][j]<<' ';
    		cout<<'\n';
    	}
    	return 0;
    }
    

    矩阵快速幂的实际应用 。例题:
    在这里插入图片描述
    如果单纯的递推的话一定会T,故考虑矩阵快速幂来优化。
    使用矩阵快速幂来优化,最重要的一步便是,构造常系数矩阵。
    我们要将递推的运算转化成矩阵来运算。
    在这里插入图片描述

    #include<bits/stdc++.h>
    using namespace std;
    typedef long long int LL;
    const int N=15;
    const int mod=10000;
    struct node{LL a[N][N];}ans,a;
    int f[15]={0,1};
    node mul1(node a,node b,LL p) 
    {
    	node c={0};
    	for(int i=1;i<=1;i++)
    	    for(int k=1;k<=2;k++)
    			for(int j=1;j<=2;j++)
    				c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j])%p;
    	return c;
    }
    node mul2(node a,node b,LL p) 
    {
    	node c={0};
    	for(int i=1;i<=2;i++)
    		for(int k=1;k<=2;k++)
    			for(int j=1;j<=2;j++)
    				c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j])%p;
    	return c;
    }
    node qsm(node a,LL b,LL p)
    {
    	node sum={0}; 
    	sum.a[1][1]=1,sum.a[1][2]=1;
    	while(b)
    	{
    		if(b&1) sum=mul1(sum,a,p);
    		b>>=1;
    		a=mul2(a,a,p);
    	}
    	return sum;
    }
    int main(void)
    {
    	LL n;
    	while(cin>>n,n!=-1)
    	{
    		a.a[1][1]=1,a.a[1][2]=1;
    		a.a[2][1]=1,a.a[2][2]=0;
    		if(n<=2) cout<<f[n]<<'\n';
    		else
    		{
    			ans=qsm(a,n-2,mod);
        		cout<<ans.a[1][1]<<'\n';
    		}
    	}
    	return 0;
    }
    

    例题二:
    在这里插入图片描述
    在这里插入图片描述
    故求斐波那契的第n项和第n+1项求一个乘积即可。

    #include<bits/stdc++.h>
    using namespace std;
    typedef long long int LL;
    const int N=15;
    const int mod=1e9+7;
    struct node{LL a[N][N];}a,ans;
    int f[15]={0,1};
    node mul1(node a,node b,LL p) 
    {
    	node c={0};
    	for(int i=1;i<=1;i++)
    	    for(int k=1;k<=2;k++)
    			for(int j=1;j<=2;j++)
    				c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j])%p;
    	return c;
    }
    node mul2(node a,node b,LL p) 
    {
    	node c={0};
    	for(int i=1;i<=2;i++)
    		for(int k=1;k<=2;k++)
    			for(int j=1;j<=2;j++)
    				c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j])%p;
    	return c;
    }
    node qsm(node a,LL b,LL p)
    {
    	node sum={0}; 
    	sum.a[1][1]=1,sum.a[1][2]=1;
    	while(b)
    	{
    		if(b&1) sum=mul1(sum,a,p);
    		b>>=1;
    		a=mul2(a,a,p);
    	}
    	return sum;
    }
    int main(void)
    {
    	LL n; cin>>n;
    	a.a[1][1]=1,a.a[1][2]=1;
    	a.a[2][1]=1,a.a[2][2]=0;
    	if(n==1) puts("1");
    	else
    	{
    		ans=qsm(a,n-1,mod);
        	cout<<(ans.a[1][1]*ans.a[1][2])%mod<<'\n';
        }
    	return 0;
    }
    

    例题三:
    在这里插入图片描述
    在这里插入图片描述

    #include<bits/stdc++.h>
    using namespace std;
    typedef long long int LL;
    const int N=15;
    const int mod=1e9+7;
    struct node{LL a[N][N];}ans,a;
    int t; 
    node mul1(node a,node b,LL mod)
    {
    	node c={0};
    	for(int i=1;i<=1;i++)
    		for(int k=1;k<=3;k++) 
    			for(int j=1;j<=3;j++)
    				c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j])%mod;
    	return c;
    }
    node mul2(node a,node b,LL mod)
    {
    	node c={0};
    	for(int i=1;i<=3;i++)
    		for(int k=1;k<=3;k++) 
    			for(int j=1;j<=3;j++)
    				c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j])%mod;
    	return c;
    }
    node qsm(node a,LL b,LL p)
    {
    	node sum={0};
    	sum.a[1][1]=1,sum.a[1][2]=1,sum.a[1][3]=1;
    	while(b) 
    	{
    		if(b&1) sum=mul1(sum,a,mod);
    		b>>=1;
    		a=mul2(a,a,p);
    	}
    	return sum;
    }
    int main(void)
    {
    	cin>>t;
    	while(t--)
    	{
    		LL n; cin>>n;
    		if(n<=3) cout<<1<<'\n';
    		else
    		{
    			a.a[1][1]=1,a.a[1][2]=1,a.a[1][3]=0;
    			a.a[2][1]=0,a.a[2][2]=0,a.a[2][3]=1;
    			a.a[3][1]=1,a.a[3][2]=0,a.a[3][3]=0;
    			ans=qsm(a,n-3,mod);
    			cout<<ans.a[1][1]<<'\n';
    		}
    	}
    	return 0;
    }
    
    展开全文
  • 快速幂: int fastpow(int base,int n,int mod){ int ans=1; while(n){ if(n&1) ans*=base%mod; base*=base; n>>=1; } return ans%mod; } 取模是避免溢出,因为幂运算结果可能太大。同模...
  • 大家好,我是bigsai,之前有个小老弟问到一个剑指offer一道相关快速幂的题,这里梳理一下讲一下快速幂快速幂是什么? 顾名思义,快速幂就是快速算底数的n次幂。你可能疑问,求n次幂算n次叠乘不就行了?当n巨大...
  • 矩阵快速幂求斐波那契数列第n项,递推公式 进而转换为矩阵幂次 矩阵快速幂代码 //矩阵快速幂计算 a^n #include <bits/stdc++.h> using namespace std; int mod=1e9+7; //模数 long long n; ...
  • 利用了矩阵结合律,先算出构造递推矩阵自乘的结果,再与初始矩阵相乘。 #include using namespace std; typedef long long ll; #define ls (o<<1) #define rs (o<<1|1) #define pb push_back //#define...
  • 文章目录一、快速幂算法(概述)二、整数快速幂(源码)三、矩阵快速幂(源码)四、矩阵快速幂的应用1.矩阵构造举例:2.例题: 一、快速幂算法(概述) ①快速幂就是快速算底数的n次幂。其时间复杂度为 O(log₂N),...
  • 有关矩阵快速幂的题都记录在此,持续更新~ 文章目录笔记1137.第N个泰波那契数 笔记 矩阵快速幂原理: 如果现在要算X8 一般思路: 即XXXXXXXX一个一个往上面乘,则乘法运算进行7次。 换个思路: 采用(XX)(XX)(XX)...
  • 矩阵乘法和矩阵快速幂

    千次阅读 2020-03-10 23:02:38
    本文主要讲解矩阵乘法和矩阵快速幂。 矩阵 数学上,一个m×n{\displaystyle m\times n}m×n的矩阵是一个由mmm行(row)n列(column)元素排列成的矩形阵列。矩阵里的元素可以是数字、符号或数学式。以下是一个由6个...
  • } 快速幂代码: public static int[][] fastPow(int[][] num, long k) {//矩阵快速幂 int[][] res = new int[3][3]; for(int i=0;i;i++) res[i][i] = 1;//单位矩阵,相当于数字快速幂的1 while(k>0) { ...
  • 文章目录矩阵概念什么是矩阵矩阵运算矩阵乘法 矩阵概念 什么是矩阵 在数学中,矩阵(Matrix)是一个按照长方阵列排列的复数或实数集合 矩阵运算 矩阵加法减法比较简单这里就不过多介绍了,主要说一下矩阵乘法, 矩阵...
  • 首先是矩阵乘法 在矩阵乘法中满足以下运算律: 1.(AB)C=a(BC) 2.(A+B)C=AC+BC 3.C(A+B)=CA+CB 在普通的乘法中,一个数乘1还是等于它本身,在矩阵乘法中也有这么一个“1”,它就是单位矩阵 不同于普通乘法中的...
  • 快速幂和矩阵快速幂1

    2022-08-03 22:15:25
    快速幂和矩阵快速幂1
  • 矩阵快速幂模板: #include<bits/stdc++.h> using namespace std; #define ll long long #define mod 1000000007 struct matrix { ll cell[5][5]; matrix(ll a=0,ll b=0,ll c=0,ll d=0) { cell[0][0]=a;...
  • 目录C.[矩阵快速幂求线性递推]考验题意样例样例输入:样例输出:思路总结代码B.[拓扑排序]猫猫向前冲题意样例样例输入:样例输出:思路总结代码C.[SCC缩点]区间选点②题意样例样例输入:样例输出:思路总结代码 ...
  • 矩阵快速幂计算斐波那契数列

    万次阅读 2022-05-01 18:10:35
    递推式和矩阵乘法 斐波那契数列有递推公式 Fn+2=Fn+1+Fnn∈N F_{n+2}=F_{n+1}+F_{n} \enspace n \in \mathbb{N} Fn+2​=Fn+1​+Fn​n∈N 我们可以把这个计算过程抽象成一个矩阵运算的过程。 [Fn+2Fn+1]=[1110]⋅[Fn+...
  • 整数快速幂: 分解成二进制形式易得程序 int fastpow(int base,int n,int mod){ int ans=1; while(n){ ...矩阵快速幂: 把整数乘法改成矩阵乘法,原理一样 struct Mat{ double m[maxn+5][maxn+5];
  • 一、快速幂 1.介绍详情 https://blog.csdn.net/qq_19782019/article/details/85621386 2.快速幂模板 (1) 简单模板,便于理解 long long fastPower(long long base, long long power) { long long result = 1; while...
  • 矩阵快速幂算法详细解析

    千次阅读 多人点赞 2020-06-01 23:19:14
    矩阵的乘法是需要矩阵A的行数与矩阵B的列数相等的(A*B的前提条件)但矩阵快速幂一般只用到方阵(行数和列数相等的情况),从而避免了前提条件。 如: [A11A12⋯A1nA21A22⋯A2n⋮⋮⋱⋮An1An2⋯Ann][B11B12⋯B1nB21...
  • 依次看后边矩阵的每一项,看它可以由前边矩阵里边的每一项怎么凑出来,会发现 a2​=a2​,a3​=a1​+a2​,所以构造一个 2×2 的矩阵 A=[0,1,1,1​] ,这样就可以按照矩阵乘法递推,然后用矩阵快速幂解决问题了。...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 33,537
精华内容 13,414
关键字:

矩阵快速幂