题解 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} $T=\begin{bmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}

Q：那所以对于一般性题目怎么做呢？

A：首先，观察累加中的每一项，然后有几项就有几行，接下来再列出这个矩阵将会变成什么矩阵，按照递推关系写上系数即可（一般来说不是最后一项的都是一堆0加一个1）

本题代码：（代码中矩阵与讲解中的对称，谨慎Copy）

#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;
}