题解 P2020 【[NOI2011]兔农】

· · 题解

分析：矩乘快速幂+规律+公式

　　考虑斐波那契数列递推，肯定是矩乘，但是在模k意义下为1时需要减一，这似乎不能直接矩乘了。考虑在每次模k等于1之前进行矩乘快速幂，做到模k等于1的时候就特殊处理，再进行同样的操作。 　　以样例的k=7做个说明，以下为模k意义下的数：　 　 1,1,2,3,5,0, 　　5,5,3,0, 　　3,3,6,2,0, 　　2,2,4,6,3,2,5,0,5,5,3,0, 　　3,3,6,2,0, 　 　　是不是很有规律？

解法

　　会发现每行第一个数是上一行最后一个非0数（这不是废话吗，0+任何数=自己啊...），而这一行的第i个数=第一个数×斐波那契数列的第i个数取模即可得到。

　　这就在暗示我们或许可以做了！令这一行的长度为len，那么第一个数×fib[len]=1(mod k)，我们可以通过已知得到fib[len] 的值，假如我们预处理出斐波那契数列在模k意义下的值，就可以做出每个模第一次出现的位置，就从而得到长度。所以只要对第一个数求个逆元就可以了，但是模数可能不是质数...那就上exgcd！当然如果没有逆元，意味着可以直接快速幂结束了...

　　但是这似乎还是会T，观察到上述序列很有可能出现循环节！就比如样例中的这个序列，我们没有必要反复计算，可以考虑一个循环节视为一个整体，对这个整体矩乘快速幂，剩下的零头再单独做，就可以完美解决这道题了。　　

AC代码（比较乱，大佬勿喷）

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
typedef long long LL;
const int inf = (1<<30);
const int MAXN = 1000011;
const int MAXL = 6000011;
LL n,fir;
int k,MOD;
int fib[MAXL],vis[MAXN],len[MAXN];
LL F[MAXN];//每个开头的数对应的使得其最后一个数为1的斐波那契数
bool hav[MAXN];//这个k意义下的模数作为开头是否出现过
struct matrix{
    int n,m;
    LL s[3][3];
}ans,ini,dan,mul,jian,I,old[MAXN];

inline matrix operator * (matrix a,matrix b){
    matrix tmp=ini; tmp.n=a.n; tmp.m=b.m;
    for(int i=0;i<a.n;i++) 
    for(int j=0;j<b.m;j++) 
        for(int l=0;l<a.m;l++)
        tmp.s[i][j]+=a.s[i][l]*b.s[l][j],tmp.s[i][j]%=MOD;
    return tmp;
}

inline int getint()
{
    int w=0,q=0; char c=getchar();
    while((c<'0' || c>'9') && c!='-') c=getchar(); if(c=='-') q=1,c=getchar(); 
    while (c>='0' && c<='9') w=w*10+c-'0', c=getchar(); return q ? -w : w;
}
inline LL gcd(LL x,LL y){ if(y==0) return x; return gcd(y,x%y); }
inline matrix fast_pow(matrix a,LL y){ matrix tmp=dan; while(y>0) { if(y&1) tmp=tmp*a; a=a*a; y>>=1; } return tmp;  }
inline LL exgcd(LL aa,LL bb,LL &x,LL &y){
    if(bb==0) {
    x=1; y=0;
    return aa;
    }    
    LL cun=exgcd(bb,aa%bb,x,y),lin=x;
    x=y; y=lin-(aa/bb)*y;
    return cun;
}
inline void out(){ if(n!=0) ans=ans*fast_pow(mul,n); ans.s[0][1]%=MOD; ans.s[0][1]+=MOD; ans.s[0][1]%=MOD; printf("%lld",ans.s[0][1]); exit(0); }
inline void work(){
    scanf("%lld",&n); k=getint(); MOD=getint(); fib[1]=fib[2]=1;
    for(int i=3;;i++) {//斐波那契数列的模k意义下的循环节不超过6*k
    fib[i]=fib[i-1]+fib[i-2]; fib[i]%=k;
    if(!vis[fib[i]]) vis[fib[i]]=i;
    if(fib[i-1]==1 && fib[i]==1) break;
    }
    for(int i=0;i<3;i++) for(int j=0;j<3;j++) ini.s[i][j]=0; for(int i=0;i<3;i++) dan.s[i][i]=1; jian=dan; ans.s[0][0]=ans.s[0][2]=1;
    ans.n=1; ans.m=3; mul.n=mul.m=jian.n=jian.m=dan.n=dan.m=3; bool FFF=false;
    mul.s[0][1]=mul.s[1][0]=mul.s[1][1]=mul.s[2][2]=1; jian.s[2][1]=-1; fir=1; LL xx,yy,gg; 
    for(;n;) {
    if(F[fir]==0) {
        gg=gcd(fir,k); if(gg!=1) F[fir]=-1;
        else { exgcd(fir,k,xx,yy); xx%=k; xx+=k; xx%=k;/*exgcd!!!*/ F[fir]=xx;  }
    }
    if(F[fir]==-1) out();
    if(!hav[fir] || FFF) {//未出现过
        if(!vis[F[fir]]) out();//不存在这种模数
        len[fir]=vis[F[fir]];//出现的第一个位置             
        if(n>=len[fir]) {
        old[fir]=fast_pow(mul,len[fir]);
        n-=len[fir];
        }
        else out();
        old[fir]=old[fir]*jian; 
        ans=ans*old[fir];
        hav[fir]=1;  fir*=fib[len[fir]-1]; fir%=k; 
    }
    else{//出现循环节        
        LL ff=fir; LL cnt=0/*!!!*/;//统计计算的次数
        I=dan;
        for(ff=fir*fib[len[fir]-1]%k;ff!=fir;(ff*=fib[len[ff]-1])%=k){
        I=I*old[ff]; cnt+=len[ff]; 
        }        
        cnt+=len[ff]; I=old[ff]*I;/*矩乘不满足交换律！！！*///I=I*old[ff];
        ans=ans*fast_pow(I,n/cnt);
        n=n%cnt; FFF=true;//标记
    }
    }
    out();
}

int main()
{
    work();
    return 0;
}