传送门:

洛谷


Solution

[洛谷1962]斐波那契数列理,只是转移方程变成了f_i=pf_{i-1}+qf_{i-2}而已,那么我们只需要将辅助转移矩阵变为下面这样就可以了:
\left[ \begin{matrix} p & q\\ 1 & 0 \\ \end{matrix} \right]

Code

/*Program from Luvwgyx*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long
#define write(x) printf("%lld\n",x)
using namespace std;
int mod;
int 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;
}
struct Matrix{
    int a[3][3];
    Matrix(){memset(a,0,sizeof(a));}
    void init(){
        memset(a,0,sizeof(a));
        for(int i=1;i<3;i++)a[i][i]=1;
    }
}init;
Matrix mul(Matrix a,Matrix b){
    Matrix c;
    for(int i=1;i<3;i++)
        for(int j=1;j<3;j++)
            for(int k=1;k<3;k++)
                c.a[i][j]=(c.a[i][j]+1ll*a.a[i][k]*b.a[k][j]%mod)%mod;
    return c;
}
Matrix add(Matrix a,Matrix b){
    Matrix c;
    for(int i=1;i<3;i++)
        for(int j=1;j<3;j++)
            c.a[i][j]=(a.a[i][j]+b.a[i][j])%mod;
    return c;
}
Matrix power(Matrix a,int b){
    Matrix ret;ret.init();
    for(;b;b>>=1,a=mul(a,a))
        if(b&1)ret=mul(ret,a);
    return ret;
}
signed main(){
    Matrix now;now.a[1][1]=read();now.a[1][2]=read();now.a[2][1]=1;
    init.a[2][1]=read();init.a[1][1]=read();
    int n=read();mod=read();
    if(n==1){write(init.a[1][1]);return 0;}
    if(n==2){write(init.a[2][1]);return 0;}
    write(mul(power(now,n-2),init).a[1][1]);
    return 0;
}

发表评论