题解 P1349 【广义斐波那契数列】

### 正解：矩阵乘法 ### UPD：LATEX修改完成 这是一种非常神奇的解法，一般来说用来写递推 比如本题，就是一道非常优秀的模板题。 如果按照$f[i]=pf[i-1]+qf[i-2]$来算会导致TLE 那么我们这时候就可以将递推转为累乘，然后利用快速幂即可得到最终答案。 $A=\begin{bmatrix} f_i \\ f_{i-1} \end{bmatrix}$ 这是原始的矩阵，下面我们要把它变成： $A'=\begin{bmatrix} f_{i+1} \\ f_i \end{bmatrix}$ 我们要乘以一个矩阵，因为1列2行的矩阵乘以它之后仍得1列2行，故这个矩阵是2列2行的 $T=\begin{bmatrix}a & b\\ c & d \end{bmatrix}$ 根据矩阵乘法的定义，可得$f_{i+1}=pf_i+qf_{i-1}=af_i+bf_{i-1}$ 故$a=p,b=q$ 同理，$f_i=cf_i+df_{i-1}$，易得$c=1,d=0$，所以我们要乘以 $T=\begin{bmatrix}p & q\\ 1 & 0 \end{bmatrix}$ 然后因为$A'=AT$，可以得到$A_n=A_1T^{n-1}$，运算量主要在后面，所以使用快速幂，时间复杂度$O(logn)$ #### Q：如果是$f_i=f_{i-1}+f_{i-2}+1$怎么办？ #### A：在矩阵里面添一项1 即： $A=\begin{bmatrix} f_i \\ f_{i-1} \\ 1 \end{bmatrix}$ $A'=\begin{bmatrix} f_{i+1} \\ f_i \\ 1 \end{bmatrix}$ $f$之间的推导仍然不变，计算$f_{i+1}$的时候记得算上一个1，同时1只要一直不变即可 $T=\begin{bmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}$ #### Q：那所以对于一般性题目怎么做呢？ #### A：首先，观察累加中的每一项，然后有几项就有几行，接下来再列出这个矩阵将会变成什么矩阵，按照递推关系写上系数即可（一般来说不是最后一项的都是一堆0加一个1） 本题代码：（代码中矩阵与讲解中的对称，谨慎Copy） ------------ ```cpp #include<bits/stdc++.h> #define maxn (10+5) using namespace std; long long mod; struct matrix { long long a[maxn][maxn],r,c; void init() { memset(a,0,sizeof(a)); } void one() { memset(a,0,sizeof(a)); for (int i=1;i<=r;++i) a[i][i]=1; } }A,Tb; matrix operator * (matrix x,matrix y) { matrix ans; ans.init(); ans.r=x.r,ans.c=y.c; for (int k=1;k<=x.c;++k) for (int i=1;i<=x.r;++i) for (int j=1;j<=y.c;++j) ans.a[i][j]=(ans.a[i][j]+(x.a[i][k]*y.a[k][j])%mod)%mod; return ans; } matrix operator ^ (matrix x,long long k) { matrix ans; ans.init(); ans.r=ans.c=x.r; ans.one(); while (k) { if (k%2==1) ans=ans*x; x=x*x; k/=2; } return ans; } int main() { long long n,p,q; cin >> p >> q >> A.a[1][1] >> A.a[1][2] >> n >> mod; A.r=1; A.c=2; // puts("GG"); if (n<3) puts("1"); else { n-=2; Tb.c=Tb.r=2; Tb.a[1][1]=0; Tb.a[1][2]=q; Tb.a[2][1]=1; Tb.a[2][2]=p; // puts("GG"); Tb=Tb^n; A=A*Tb; cout << A.a[1][2] << endl; } return 0; } ```