目录
【急速幂】
【导线安装】
【应用】
【行列的高速乘方】
【矩阵乘法】
【导线安装】
【应用】
【高速幂】高速幂用于有效求出(a^b ) mod n的结果。
考虑分治思想，当b为偶数时，可以将a^b转换为a^(b/2 ) a^(b/2 ) b/2 )，当b为奇数时，可以将a^b转换为a^(b/2 ) a^(b/2 ) ) a ) a。 这样，最终b变为1，只需要logb次的运算。
【代码实现】//两种写法intquick_pow(inta、int b、int mod )//递归(if(b==1) return a； intt=quick_pow(a，b/2，mod )； t=t*t%mod； if(B1 ) t=t*a%mod； 返回t； }intquick_pow(inta、int b、int mod ) /非递归) { int ret=1； while(b ) ) if ) B1 ) ret=ret*a%mod； a=a*a%mod； b=b/2； }返回ret； }【应用】虽然省略了说明，但这是高效求出(a^b ) mod n的结果。
【矩阵的快速幂】预备知识：矩阵乘法
【矩阵乘法】常数int n=100； int c[N][N]； voidmulti(inta ()、int n )、int n )、int n )/n是矩阵的大小(memset(c，0，sizeof(c ) )； for(intI=1； i=n； I ) for(intj=1； j=n； j ) for(intk=1； k=n； k ) c[i][j]=a[i][k]*b[k][j]； }将高速乘方算法的乘法变为矩阵的乘法是矩阵的高速乘方。
【代码实现】常数int n=100； int tmp[N][N]； voidmulti(inta ()、int n )、int n、j、k； 短信(tmp，0，sizeof tmp )； for(I=0； in； I ) for ) j=0； jn； j ) for ) k=0； kn； k ) tmp[i][j]=a[i][k]*b[k][j]； for(I=0； in； I ) for ) j=0； jn； j ) a[i][j]=tmp[i][j]； }int res[N][N]； voidpow(inta[][n]，int n ) memset ) RES，0，sizeof res )； //n为幂，n为矩阵大小for(intI=0； iN； I ) res[i][i]=1； while(n ) ) if ) N1 ) multi ) RES，a，n )； //res=res*a； 多重(a，a，n )； //a=a*a n=1； }【应用】矩阵的快速幂可用于优化递归。
矩阵快速幂是如何优化递推的呢？
首先，构造适当的初始状态(第一个矩阵)，然后利用这个矩阵和矩阵乘法的性质，生成快速幂的
手段求出之后的状态。构造矩阵可以根据矩阵乘法的实现特点来构造，利用合适的性质可以简化运算。如何构造矩阵呢？
（一）f[n]=f[n-1]+f[n-2],f[1]=f[2]=1的第n项快速求法
考虑1×2的矩阵【f[n-2],f[n-1]】。
根据Fibonacci数列的递推关系，我们可以通过乘以一个2×2的矩阵A，得到矩阵：【f[n-1],f[n]】。
即：【f[n-2],f[n-1]】*A = 【f[n-1],f[n]】=【f[n-1],f[n-1]+f[n-2]】
很容易构造出这个2×2矩阵A，即：
０ １
１ １
所以，有【f[1],f[2]】×A＝【f[2],f[3]】
又因为矩阵乘法满足结合律，故有：【f[1],f[2]】×A ^(n-1) =【f[n],f[n+1]】
这个矩阵的第一个元素f[n]即为所求。
（二）f[n]=f[n-1]+f[n-2]+1,f[1]=f[2]=1的第n项的快速求法
考虑1×3的矩阵【f[n-2],f[n-1],1】。
期望求得某3×3的矩阵A，使得此1×3的矩阵乘以A得到矩阵：【f[n-1],f[n],1】
即：【f[n-2],f[n-1],1】* A ＝【f[n-1],f[n],1】=【f[n-1],f[n-1]+f[n-2]+1,1】
容易构造出这个3×3的矩阵A，即：
０ １ ０
１ １ ０
０ １ １
故：【f[1],f[2],1】* A^(n-1) = 【f[n],f[n+1],1】
（三）数列f[n]=f[n-1]+f[n-2]+n+1,f[1]=f[2]=1的第n项的快速求法
考虑1×4的矩阵【f[n-2],f[n-1],n,1】。
期望求得某4×4的矩阵A，使得此1×4的矩阵乘以A得到矩阵：【f[n-1],f[n],n+1,1】
即：【f[n-2],f[n-1],n,1】* A = 【f[n-1],f[n],n+1,1】＝【f[n-1],f[n-1]+f[n-2]+n+1,n+1,1】
容易构造出这个4×4的矩阵A，即：
０ １ ０ ０
１ １ ０ ０
０ １ １ ０
０ １ １ １
故：【f[1],f[2],3,1】* A^(n-1) = 【f[n],f[n+1],n+2,1】
（四）数列f[n]=f[n-1]+f[n-2],f[1]=f[2]=1的前n项和s[n]=f[1]+f[2]+……+f[n]求法
考虑1×3的矩阵【f[n-2],f[n-1],s[n-2]】。
期望通过乘以一个3×3的矩阵A，得到1×3的矩阵：【f[n-1],f[n],s[n-1]】
即：【f[n-2],f[n-1],s[n-2]】 * A = 【f[n-1],f[n],s[n-1]】=【f[n-1],f[n-1]+f[n-2],s[n-2]+f[n-1]】
容易得到这个3×3的矩阵A是：
０ １ ０
１ １ １
０ ０ １
这种方法的矩阵规模是(r+1)*(r+1)
f(1)=f(2)=s(1)=1 ，所以，有【f(1),f(2),s(1)】* A = 【f(2),f(3),s(2)】
故：【f(1),f(2),s(1)】* A^(n-1) = 【f(n),f(n+1),s(n)】
（五）数列f[n]=f[n-1]+f[n-2]+n+1,f[1]=f[2]=1的前n项和s[n]=f[1]+f[2]+……+f[n]求法
考虑1×5的矩阵【f[n-2],f[n-1],s[n-2],n,1】
我们需要找到一个5×5的矩阵A，使得它乘以A得到如下1×5的矩阵【f[n-1],f[n],s[n-1],n+1,1】
即：【f[n-2],f[n-1],s[n-2],n,1】* A =【f[n-1],f[n],s[n-1],n+1,1】=【f[n-1], f[n-1]+f[n-2]+n+1,s[n-2]+f[n-1],n+1,1】
容易构造出A为：
０ １ ０ ０ ０
１ １ １ ０ ０
０ ０ １ ０ ０
０ １ ０ １ ０
０ １ ０ １ １
故：【f(1),f(2),s(1),3,1】* A^(n-1) = 【f(n),f(n+1),s(n),n+2,1】
（六）f[n]=p*f[n-1]+q*f[n-2]+r*n+s
可以构造矩阵A为：
0 q 0 0 0
1 p 1 0 0
0 0 1 0 0
0 r 0 1 0
0 s 0 1 1
（七）f[n]=Sigma(a[n-i]*f[n-i])+Poly(n)
其中0<i<=某常数c, Poly (n)表示n的多项式，我们依然可以构造类似的矩阵A来解决问题。
设Degree(Poly(n))=d, 并规定Poly(n)=0时，d=-1，此时对应于常系数线性齐次递推关系。则本方法求前n项和的复杂度为：((c+1)+(d+1))3*logns
例如：A(0) = 1 , A(1) = 1 , A(N) = X * A(N - 1) + Y * A(N - 2) (N >= 2)；
给定三个值N，X，Y求S(N):S(N) = A(0)2 +A(1)2+……+A(n)2。
解：
考虑1*4 的矩阵【s[n-2],a[n-1]^2,a[n-2]^2,a[n-1]*a[n-2]】
我们需要找到一个4×4的矩阵A，使得它乘以A得到1×4的矩阵
【s[n-1],a[n]^2,a[n-1]^2,a[n]*a[n-1]】
即：【s[n-2],a[n-1]^2,a[n-2]^2,a[n-1]*a[n-2]】* A = 【s[n-1],a[n]^2,a[n-1]^2,a[n]*a[n-1]】= 【s[n-2]+a[n-1]^2 , x^2 * a[n-1]^2 + y^2 * a[n-2]^2 + 2*x*y*a[n-1]*a[n-2]，a[n-1]^2 , x*a[n-1]^2 + y*a[n-2]a[n-1]】
可以构造矩阵A为：
1 0 0 0
1 x^2 1 x
0 y^2 0 0
0 2xy 0 y
故：【S[0],a[1]^2,a[0]^2,a[1]*a[0]】 * A^(n-1) = 【s[n-1],a[n]^2,a[n-1]^2,a[n]*a[n-1]】
所以：【S[0],a[1]^2,a[0]^2,a[1]*a[0]】 * A^(n) = 【s[n],a[n+1]^2,a[n]^2,a[n+1]*a[n]】
若A = (B * C ) 则AT = ( B * C )T = CT * BT
故可得如下图所示的矩阵：
【引用参考来自】
数论常用内容——矩阵快速幂