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

邓布利多6 · 2019-09-01 12:02:30 · 题解

部分分做法

普通斐波那契数列：

for(int i=3;i<=n;i++)
    f[i]=f[i-1]*p+f[i-2]*q;
cout<<f[n];

这就写好了，结果TLE了。

AC做法：

矩阵乘法+快速幂

不难得出：

        f（n）     1 1   f（n-1）
        f（n-1）=  1 0 * f（n-2）

所以定义结构体

struct matrix
{
    long long num[3][3];
    matrix()
    {
        memset(num,0,sizeof num);
    }
};

加上矩阵乘法

//放在结构体内部
matrix operator * (const matrix a) const
    {
        matrix b;
        for(int i=1;i<=2;i++)
            for(int j=1;j<=2;j++)
                for(int k=1;k<=2;k++)
                    b.num[i][j]=(b.num[i][j]+num[i][k]%mod*a.num[k][j])%mod;
        return b;
    }

最后是快速幂

matrix pow(matrix a,long long int k)
{
    matrix b=a;
    k--;
    while(k)
    {
        if(k%2)b=b*a;
        a=a*a;
        k/=2;
    }
    return b;
}

完整代码如下

#include<iostream>
#include<memory.h>
using namespace std;
int p,q,a1,a2;
long long int n,mod;
struct matrix
{
    long long num[3][3];
    matrix()
    {
        memset(num,0,sizeof num);
    }
    matrix operator * (const matrix a) const//运算符重载
    {
        matrix b;
        for(int i=1;i<=2;i++)
            for(int j=1;j<=2;j++)
                for(int k=1;k<=2;k++)
                    b.num[i][j]=(b.num[i][j]+num[i][k]%mod*a.num[k][j])%mod;
        return b;
    }
}a,b,c;
matrix pow(matrix a,long long int k)
{
    matrix b=a;
    k--;
    while(k)
    {
        if(k%2)b=b*a;
        a=a*a;
        k/=2;
    }
    return b;
}
int main()
{
    cin>>p>>q>>a1>>a2>>n>>mod;
    if(n==1)cout<<a1<<endl;
        else if(n==2)cout<<a2<<endl;
            else {
                //构造矩阵
                b.num[1][1]=a1; 
                b.num[1][2]=a2;
                a.num[2][1]=1;
                a.num[1][2]=q;
                a.num[2][2]=p;
                //矩阵乘法
                c=b*pow(a,n-1);
                cout<<c.num[1][1]<<endl;
            }
    return 0;
}