矩阵快速幂-补充

矩阵快速幂除了用于矩阵的乘法之外，还用于递推式的运算，比如1e7的数组无法存下，可以用矩阵快速幂把递推式化为矩阵，然后矩阵快速幂，例如下列式子。

b[i]=2*b[i-1]+a[i-1]; a[i]=3*b[i-1];

a[i-1]=3*b[i-2];

b[i]=2*b[i-1]+3*b[i-2];

b[i+2]=2*b[i+1]+3*b[i];

再根据

EXAMPLE：

  递推式： d(n + 2) = p * d(n + 1) + (1 - p) * d(n);

  令G(n) = (d(n + 2), d(n + 1))^T;

  则 G(n + 1) = M * G(n);

  解得 M = p   1 - p

               1    0

  G(n) = (M ^ n) * G(0);

#

得p=2 1-p=3

也就是得a=(3,2) b=(0,1)

           (3,2)

用矩阵乘法表示的话 （横*竖） 3*0+2*3     3*1+2*2

已经很清楚了。找到了递推式，代模版