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

· · 题解

非常显然的矩阵快速幂……

p,1 对 q,0 这个矩阵做快速幂取模，然后和(a2,a1)相乘即可得到an

具体实现可以见代码。


#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
using namespace std;
#define LL long long
LL p,q,a1,a2,n,m;
const int delen=23,delta=1<<delen,deltb=delta-1;
LL mod_add(LL x,LL y)
{
    x+=y;
    if(x>=m) x-=m;
    return x;
}
LL mod_mul(LL x,LL y)
{
    LL ret=0;
    while(y)
    {
        if(y&deltb) ret=mod_add(ret,x*(y&deltb)%m);
        x=x*delta%m;
        y>>=delen;
    }
    return ret;
}
struct Matrix
{
    int r,c;
    LL num[5][5];
    Matrix operator * (const Matrix &x) const
    {
        Matrix ret={};
        ret.r=r;
        ret.c=x.c;
        for(int i=0;i<r;i++)
            for(int j=0;j<x.c;j++)
            {
                for(int k=0;k<c;k++) ret.num[i][j]+=mod_mul(num[i][k],x.num[k][j]);
                ret.num[i][j]%=m;
            }
        return ret;
    }
    Matrix pow(LL k) const
    {
        Matrix ret={},tmp=*this;
        ret.r=ret.c=r;
        for(int i=0;i<r;i++) ret.num[i][i]=1;
        while(k)
        {
            if(k&1) ret=ret*tmp;
            tmp=tmp*tmp;
            k>>=1;
        }
        return ret;
    }
}A;
inline LL read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int main()
{
    //freopen("test.txt","r",stdin);
    p=read();q=read();a1=read();a2=read();
    n=read();m=read();
    A.num[0][0]=p,A.num[1][0]=q,A.num[0][1]=1,A.r=2,A.c=2;
    A=A.pow(n-2);
    Matrix B;
    B.num[0][0]=a2,B.num[0][1]=a1,B.r=1,B.c=2;
    B=B*A;
    printf("%lld\n",B.num[0][0]%m);
    return 0;
}