题解 P2020 【[NOI2011]兔农】

· · 题解

很有趣的一道题

看到这种求数列的题就感觉是矩阵快速幂

接近于求个斐波拉契数列

但是中间会有转移方程不同的地方

很烦

那么我们就可以想到通过要减一的地方分段矩阵快速幂,那就可以解决这一个问题

很显然,斐波拉契在mod\space p下是会有循环节的

那么就可以通过找到循环节然后进行分段了

但是我们还有一个性质

如果fib_{i-1}+fib_{i-2}\equiv 1\pmod k

那么fib_i=fib_{i-1}+fib_{i-2}-1

否则fib_i=fib_{i-1}+fib_{i-2}

那么我们可以发现一个有趣的性质

如果满足fib_{i-1}+fib_{i-2}\equiv 1\pmod k

那么fib_i\equiv 0 \pmod k

而且fib_{i+1}=fib_{i+2}

那么我们把fib_i\equiv 0\pmod k的数拿来分段

我们可以发现每一段的数都是数列普通斐波拉契与一个数的乘积

那么我们关键便是找出这个数字

我们发现他满足同余方程x*fib_j \equiv1 \pmod{k}

那么我们只要预处理出所有的fib_j的逆元即可

然后通过矩阵快速幂分段搞即可,矩阵也很好推

#include<bits/stdc++.h>
#define re return
#define ll long long
#define N 2000011
using namespace std;
ll n,k,p;
struct Jack{
    ll f[4][4];
    Jack(){memset(f,0,sizeof(f));}
    inline Jack operator *(const Jack &b)const{
        Jack ans;
        int i,j,k;
        for(k=1;k<=3;++k)
        for(i=1;i<=3;++i)
        for(j=1;j<=3;++j)
        ans.f[i][j]=((ans.f[i][j]+f[i][k]*b.f[k][j]%p)%p+p)%p;
        re ans;
    }
    inline void one( ){
        int i,j;
        for(i=1;i<=3;++i)f[i][i]=1;
    }
    inline void pre_one( ){
        f[1][1]=f[1][2]=f[2][1]=f[3][3]=1;
    }
    inline void pre_two( ){
        pre_one( );
        f[3][1]=-1;
    }
    inline void pre_three( ){
        f[3][1]=f[3][3]=1;
    }
};
inline Jack qui(Jack a,ll b){
    Jack ans;
    ans.one( );
    while(!!b){
        if(b&1)ans=ans*a;
        a=a*a,b>>=1;
    }
    re ans;
}
inline void exgcd(ll a,ll b,ll &x,ll &y,ll &d){
    if(!b){d=a,x=1,y=0;return;}
    exgcd(b,a%b,y,x,d);
    y-=a/b*x;
}
inline ll getinv(ll a,ll p){
    ll x,y,d;
    exgcd(a,p,x,y,d);
    if(d!=1)re -1;
    re (x%p+p)%p;
}
ll f[N],len[N],tot,q[N],vis[N];
int main( ){
    scanf("%lld%lld%lld",&n,&k,&p);
    int i;
    f[1]=f[2]=1;
    if(n<=2){puts("1");re 0;}
    for(i=3;i<=2e6;++i){
        f[i]=(f[i-1]+f[i-2])%k;
        if(f[i]==1&&!len[1])len[1]=i;
        ll inv(getinv(f[i],k));
        if(inv!=-1&&!len[inv])len[inv]=i;
    }
    ll now(1),t(0),l;
    int flag(0);
    while(1){
        l=len[now];
        q[++tot]=now,vis[now]=tot;
        if(!l){
            for(i=1;i<tot;++i)t+=len[q[i]];
            flag=1;
            break;
        }
        now=(now*f[l-1])%k;
        if(!!vis[now]){
            for(i=1;i<vis[now];++i)t+=len[q[i]];
            break;
        }
    }
    Jack a,tr1,tr2;
    tr1.pre_one( ),tr2.pre_two( ),a.pre_three( );
    if(n<=t){
        --len[1],--n;
        for(i=1;i<vis[now];++i)
        if(n>=len[q[i]]){
            a=a*qui(tr1,len[q[i]]-1)*tr2;
            n-=len[q[i]];
        }else{
            printf("%lld\n",(a*qui(tr1,n)).f[3][1]);
            re 0;
        }
    }else{
        --len[1];
        n-=t;
        for(i=1;i<vis[now];++i)a=a*qui(tr1,len[q[i]]-1)*tr2;
        if(!!flag){
            printf("%lld\n",(a*qui(tr1,n)).f[3][1]);
            re 0;
        }else{
            ll size(0);
            Jack tr;
            tr.one( );
            for(i=vis[now];i<=tot;++i){
                tr=tr*qui(tr1,len[q[i]]-1)*tr2;
                size+=len[q[i]];
            }
            a=a*qui(tr,n/size);
            n=n%size;
            for(i=vis[now];i<=tot;++i)
            if(n>=len[q[i]]){
                a=a*qui(tr1,len[q[i]]-1)*tr2;
                n-=len[q[i]];
            }else{

                printf("%lld\n",(a*qui(tr1,n)).f[3][1]);
                re 0;
            }
        }
    }
//  puts("WORK");
}