矩阵快速幂加速递推

Blocks(POJ 3734）矩阵快速幂　http://www.cnblogs.com/pdev/p/4063194.html
常见递推形式二举例
题目原意：N个方块排成一列，每个方块可涂成红、蓝、绿、黄。问
红方块和绿方块都是偶数的方案的个数。
假设已涂完前i个方块时，有：
na[i] = 1~i方块中，红、绿方块数量都是偶数的方案数
nb[i] = 1~i方块中，红、绿方块数量一个是偶数一个是奇数的方案数（红
even绿odd 或 红odd绿even）
nc[i] = 1~i方块中，红、绿方块数量都是奇数的方案数
且有a(0)=1； b(0)=0； c(0)=0
则涂第i+1个格子时，不难推导出：
na[i+1]=2a[i]+b[i]　　　　
nb[i+1]=2a[i]+2b[i]+2c[i]
nc[i+1]=b[i]+2*c[i]

也就是

计算A^n
// A^4能通过(A^2)*(A^2)得到，A^8又能通
过(A^4)*(A^4)得到，利用这一特性，大大减
少乘法次数
mat pow(mat A,ll n)
{ mat B;
memset(B.m,0,sizeof(B.m));
for(int i=0;i<3;i++)
{ B.m[i][i]=1; //B初始化为单位矩阵
}
while(n>0) //时间复杂度O(logn)
{
if(n&1) B=mul(B,A);
A=mul(A,A);
n>>=1;
}
return B;
}

就是把幂底数换成了矩阵
顺便熟悉一下矩阵乘法。
n阶层矩阵相乘为O（n^n）复杂度。

对，还有五行问题。。。。。

最后

以上就是调皮面包为你收集整理的矩阵快速幂加速递推的全部内容，希望文章能够帮你解决矩阵快速幂加速递推所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。