矩阵快速幂加速递推

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）复杂度。

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