矩阵快速幂

对于一个有递推式的f[n]，但是需要求的第n项n比较大时，就用矩阵快速幂

解法

1.先找到f[n]和f[n-1],f[n-2]...等的递推关系，并求出需要的初始项的值
2.再根据递推式构造出矩阵A
3.进行矩阵快速幂的计算

矩阵乘法

一个 m * n 的矩阵A(m,n)乘一个 n * p 的矩阵B(n,p),会得到一个 m * p 的矩阵c(m,p)

注意：A矩阵的列数必须等于B矩阵的行数

结果C是一个m行p列的矩阵，其中第i行第j列就是A矩阵第i行所有的数分别与B矩阵第j列所有的数相乘后所得的n个乘积的和

$\begin{pmatrix} A1 & A2 \\ A3 & A4 \end{pmatrix}$*$\begin{pmatrix} B1 & B2 \\ B3 & B4 \end{pmatrix}$ =$\begin{pmatrix} C1 & C2 \\ C3 & C4 \end{pmatrix}$

那么对于上式，$C1=A1*B1+A2*B3$

矩阵乘法满足结合律和分配率
结合律：$(AB)C=A(BC)$
分配率:$(A+B)C=AC+BC$

不满足交换律

矩阵快速幂的构造

假设递推式为f[n]=f[n-1]+f[n-2]

那么我们需要用A矩阵乘上一个第n-1项的矩阵构造出第n项的矩阵

即$C[n]=C[n-1]*A$

同理$C[n-1]=C[n-2]*A$

那么最终的等式就是$C[n]=C[1] * A * A *...$

即$C[n]=C[1]*A^{n-1}$ 或$C[n]=C[k]*A^{n-k}$ (A的次幂加上c的项数等于n)

那么C矩阵如何构造？

f[n]中出现的所有变量写出来(或者少一项)，如果构造途中还需要别的项，那么直接加上即可

如：f[n]=f[n-1]+f[n-2]，里面有f[n] f[n-1] f[n-2]

那么
$C[n]$= $\begin{pmatrix} f[n]&f[n-1] \end{pmatrix}$
$C[n-1]$= $\begin{pmatrix} f[n-1]&f[n-2] \end{pmatrix}$

那么根据$C[n]=C[n-1]*A$,可以构造出来A矩阵为：
$\begin{pmatrix} 1 & 1\\ 1 &0 \end{pmatrix}$

矩阵乘法

以求斐波那契f[n]=f[n-1]+f[n-2]的前n项和为例，构造的
$C[n]=\begin{pmatrix} s[n] & f[n] &f[n-1]\\ \end{pmatrix}$
$C[n-1]=\begin{pmatrix} s[n-1] & f[n-1] &f[n-2]\\ \end{pmatrix}$
那么构造出的3*3的A矩阵就是：
$A=\begin{pmatrix} 1& 0&0 \\ 1 & 1& 1\\ 1& 1&0 \end{pmatrix}$

那么我们定义出A矩阵：

const int N=3;
    int a[N][N]={
    {1,0,0},
    {1,1,1},
    {1,1,0},
    };

再定义出C[2]矩阵：

int f2[N]={2,1,1};

求A^{n-2}:

    n-=2;
    while(n){
        if(n&1)mul(f2,f2,a);
        mul(a,a,a);
        n>>=1;
    }

mul的两个函数：

void mul(int c[],int a[],int b[][N]){
	int temp[N]={0};
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			temp[i]=(temp[i]+a[j]*b[j][i])%m;
		}
	}
	memcpy(c,temp,sizeof temp);	
}
void mul(int c[][N],int a[][N],int b[][N]){
	int temp[N][N]={0};
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			for(int k=0;k<N;k++){
				temp[i][j]=(temp[i][j]+a[i][k]*b[k][j])%m;
			}
		}
	}
	memcpy(c,temp,sizeof temp);
}

最后算出的f2[0]即为s[n]，注意：因为是从第三项开始，所以我们特殊输出一下n=1和n=2的情况

几种形式的构造方法

1.形如$f[n]=f[n-1]+f[n-3]+c$

只需要在C中加入常数项1即可

$C[n]$= $\begin{pmatrix} f[n]& f[n-1]& f[n-2]& 1 \end{pmatrix}$

$C[n-1]$= $\begin{pmatrix} f[n-1]& f[n-2]& f[n-3]& 1 \end{pmatrix}$

那么构造出的A为：
$\begin{pmatrix} 1 & 1 & 0& 0 \\ 0 & 0 & 1& 0 \\ 1 & 0 & 0& 0 \\ c & 0 & 0& 1\\ \end{pmatrix}$

2.形如$f[n]=f[n-1]+f[n-2]+n^3$

二项式定理：

任意两个数和的n次方，假设一个数为x另一个数为y，那么：

$(x+y)^n=C_{n}^{n} x^n*C_{n}^{0}y^0+C_{n}^{n-1} x^{n-1} *C_{n}^{1}y^1+...+C_{n}^{0} x^0*C_{n}^{n}y^n$

将$n^{3}$用$n-1$的幂次表示出来

$n^{3}=(n-1)^{3}+3(n-1) ^{2}+3(n-1)+1$

同理$n^{2}=(n-1)^{2}+2(n-1)+1,n=(n-1)+1$

那么需要$(n-1)^{3}，(n-1) ^{2}，(n-1)，1$，我们将C[n-1]里加上这些项，即：

$C[n]=\begin{pmatrix} f[n] & f[n-1] & n^3 & n^2 & n & 1 \end{pmatrix}$

那么第n-1项的C就是：
$C[n-1]=\begin{pmatrix} f[n-1] & f[n-2] & (n-1)^3 & (n-1)^2& n-1& 1 \end{pmatrix}$

那么按照矩阵乘法的性质构造A即可

3.求f[n]的前缀和S[n]

$f[n]=f[n-1]+f[n-2]+f[n-3]$

给定任意一个l，r，求$f[l]+f[l+1]+...+f[r]$

要求的式子转换一下就是$S[r]-S[l-1]$，那么只用求出S[n]的通式再代入计算即可

$S[n]=S[n-1]+f[n]$

$f[n]=f[n-1]+f[n-2]+f[n-3]$

那么C的第n项就要有:$S[n],f[n],f[n-1],f[n-2]$

然后再结合C的第n-1项求出A矩阵即可

4.求$f[n]^2$的前缀和

$f[n]=f[n-1]+f[n-2]$

$S[n]=f[1]^{2} +f[2]^{2} +f[3]^{2} +...+f[n]^{2}$,求S[n]

$S[n]=S[n-1]+f[n]^2$
$=S[n-1]+(f[n-1]+f[n-2])^2$
$=S[n-1]+f[n-1]^2+2f[n-1]f[n-2]+f[n-2]^2$

$C[n]$= $\begin{pmatrix} s[n] & f[n]^2& f[n]f[n-1]& f[n-1]^2 \end{pmatrix}$

$C[n-1]$= $\begin{pmatrix} s[n-1] & f[n-1]^2& f[n-1]f[n-2]& f[n-2]^2 \end{pmatrix}$

难点就在于$f[n]f[n-1]$如何用$f[n-1]^2,f[n-1]f[n-2],f[n-2]^2$这几个数构造

因为$f[n]=f[n-1]+f[n-2]$,那么$f[n]f[n-1]=(f[n-1]+f[n-2])f[n-1]$

展开之后是$f[n-1]^2+f[n-1]f[n-2]$，刚好可以用上述式子构造

例题

1.有一个01字符串，任何子串不能包含101和111，求满足长度为n的字符串一共有多少（答案对1e9+7取模）

思路：

设f[i]表示长度为1~i的所有满足上述条件的字符串个数

第i位可以是0也可以是1

方案数就是第i位0的方案数加上第i位是1的方案数

当第i位为0时：那么第i-1位可以是0也可以是1，那么也就是长度为1~i-1的字符串的个数，即加上f[i-1]

当第i位为1时：
那么第i-2和i-1位能是10或11，那么就只能是01或00
当是00的时候，前面一位即第i-3位可以是0也可以是1，即加上f[i-3]
当是01的时候，前面一位即第i-3就只能是0，前面两位即i-4位可以是0也可以是1，即加上f[i-4]

那么递推式就是f[i]=f[i-1]+f[i-3]+f[i-4]

那么我们要求的就是f[n]=f[n-1]+f[n-3]+f[n-4]

然而这个n很大，不能O(n)的时间复杂度算，就需要用到矩阵快速幂

那么根据上述柿子，我们需要提前算出前4项的值

那么枚举一下很容易得到:f[1]=2 f[2]=4 f[3]=6 f[4]=10