http://www.lydsy.com/JudgeOnline/problem.php?id=2432
感觉是day1中最难的一题，还好出题人很良心，给了75分部分分。
还是跪拜策爷吧~Orz
http://jcvb.is-programmer.com/posts/39528.html
代码奇丑。。。。。。
#include<cstdio> #include<cstdlib> #include<iostream> #include<fstream> #include<algorithm> #include<cstring> #include<string> #include<cmath> #include<queue> #include<stack> #include<map> #include<utility> #include<set> #include<bitset> #include<vector> #include<functional> #include<deque> #include<cctype> #include<climits> #include<complex> //#include<bits/stdc++.h>适用于CF,UOJ，但不适用于poj using namespace std; typedef long long LL; typedef double DB; typedef pair<int,int> PII; typedef complex<DB> CP; #define mmst(a,v) memset(a,v,sizeof(a)) #define mmcy(a,b) memcpy(a,b,sizeof(a)) #define re(i,a,b) for(i=a;i<=b;i++) #define red(i,a,b) for(i=a;i>=b;i--) #define fi first #define se second #define m_p(a,b) make_pair(a,b) #define SF scanf #define PF printf #define two(k) (1<<(k)) template<class T>inline T sqr(T x){return x*x;} template<class T>inline void upmin(T &t,T tmp){if(t>tmp)t=tmp;} template<class T>inline void upmax(T &t,T tmp){if(t<tmp)t=tmp;} const DB EPS=1e-9; inline int sgn(DB x){if(abs(x)<EPS)return 0;return(x>0)?1:-1;} const DB Pi=acos(-1.0); inline int gint() { int res=0;bool neg=0;char z; for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar()); if(z==EOF)return 0; if(z=='-'){neg=1;z=getchar();} for(;z!=EOF && isdigit(z);res=res*10+z-'0',z=getchar()); return (neg)?-res:res; } inline LL gll() { LL res=0;bool neg=0;char z; for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar()); if(z==EOF)return 0; if(z=='-'){neg=1;z=getchar();} for(;z!=EOF && isdigit(z);res=res*10+z-'0',z=getchar()); return (neg)?-res:res; } const LL maxK=1000000; LL N,K,P; LL fib[6*maxK+100]; LL pos[maxK+100]; LL len[maxK+100],next[maxK+100]; inline LL gcd(LL a,LL b){return b==0 ? a : gcd(b,a%b); } inline void extend_gcd(LL a,LL &x,LL b,LL &y) { if(b==0){x=1;y=0;return;} LL dx,dy; extend_gcd(b,dx,a%b,dy); x=dy; y=dx-a/b*dy; } struct Tmatrix { int n,m; LL v[4][4]; inline void clear(){n=m=0;mmst(v,0);} inline friend Tmatrix operator *(Tmatrix a,Tmatrix b) { int i,j,k; Tmatrix c;c.clear(); c.n=a.n;c.m=b.m; re(i,1,c.n)re(j,1,c.m)re(k,1,a.m)c.v[i][j]=(c.v[i][j]+a.v[i][k]*b.v[k][j]%P)%P; return c; } }; Tmatrix A,B; inline Tmatrix power(Tmatrix a,LL k) { int i; Tmatrix x,y=a; x.clear();x.n=x.m=a.n;re(i,1,a.n)x.v[i][i]=1; for(;k!=0;k>>=1){if(k&1)x=x*y;y=y*y;} return x; } int flag[maxK+100]; int main() { /*freopen("rabbit.in","r",stdin); freopen("rabbit.out","w",stdout);*/ LL i; N=gll();K=gll();P=gll(); fib[1]=fib[2]=1; for(i=3;;i++) { fib[i]=(fib[i-1]+fib[i-2])%K; if(!pos[fib[i]])pos[fib[i]]=i; if(fib[i]==1 && fib[i-1]==1)break; } re(i,1,K-1) { LL x,y; if(gcd(i,K)==1) { extend_gcd(i,x,K,y); x=(x%K+K)%K; if(pos[x]==0) { len[i]=-1; next[i]=-1; } else { len[i]=pos[x]; next[i]=i*fib[len[i]-1]%K; } } else len[i]=-1,next[i]=-1; } A.clear(); A.n=A.m=3; A.v[1][1]=1;A.v[1][2]=1;A.v[1][3]=0; A.v[2][1]=1;A.v[2][2]=0;A.v[2][3]=0; A.v[3][1]=0;A.v[3][2]=0;A.v[3][3]=1; B.clear(); B.n=B.m=3; B.v[1][1]=1;B.v[1][2]=0;B.v[1][3]=-1; B.v[2][1]=0;B.v[2][2]=1;B.v[2][3]=0; B.v[3][1]=0;B.v[3][2]=0;B.v[3][3]=1; int p,t; for(p=1;!flag[p] && next[p]!=-1;flag[p]=1,p=next[p]); if(next[p]!=-1) { LL lenX=0,lenY=0;Tmatrix X,Y,Z; X.clear();X.n=X.m=3;X.v[1][1]=X.v[2][2]=X.v[3][3]=1; for(t=1;t!=p;t=next[t])X=B*power(A,len[t])*X,lenX+=len[t]; if(N>=lenX) { Y.clear();Y.n=Y.m=3;Y.v[1][1]=Y.v[2][2]=Y.v[3][3]=1; for(t=p,Y=B*power(A,len[t])*Y,lenY+=len[t],t=next[t];t!=p;t=next[t])Y=B*power(A,len[t])*Y,lenY+=len[t]; Z=power(Y,(N-lenX)/lenY)*X; N=(N-lenX)%lenY; for(t=p;;t=next[t]) if(N>=len[t]) { Z=B*power(A,len[t])*Z; N-=len[t]; } else break; LL y=(Z.v[1][2]+Z.v[1][3])%P,x=(Z.v[2][2]+Z.v[2][3])%P; Y.clear(); Y.n=Y.m=2; Y.v[1][1]=1;Y.v[1][2]=1; Y.v[2][1]=1;Y.v[2][2]=0; Z=power(Y,N); LL res=(Z.v[1][1]*y%P+Z.v[1][2]*x%P)%P; cout<<(res%P+P)%P<<endl; } else { X.clear();X.n=X.m=3;X.v[1][1]=X.v[2][2]=X.v[3][3]=1; for(t=1;t!=p;t=next[t]) if(N>=len[t]) { X=B*power(A,len[t])*X; N-=len[t]; } else break; LL y=(X.v[1][2]+X.v[1][3])%P,x=(X.v[2][2]+X.v[2][3])%P; Y.clear(); Y.n=Y.m=2; Y.v[1][1]=1;Y.v[1][2]=1; Y.v[2][1]=1;Y.v[2][2]=0; Z=power(Y,N); LL res=(Z.v[1][1]*y%P+Z.v[1][2]*x%P)%P; cout<<(res%P+P)%P<<endl; } } else { LL lenX=0;Tmatrix X,Y,Z; X.clear();X.n=X.m=3;X.v[1][1]=X.v[2][2]=X.v[3][3]=1; for(t=1;t!=p;t=next[t])X=B*power(A,len[t])*X,lenX+=len[t]; if(N>=lenX) { LL y=(X.v[1][2]+X.v[1][3])%P,x=(X.v[2][2]+X.v[2][3])%P; N-=lenX; Y.clear(); Y.n=Y.m=2; Y.v[1][1]=1;Y.v[1][2]=1; Y.v[2][1]=1;Y.v[2][2]=0; Z=power(Y,N); LL res=(Z.v[1][1]*y%P+Z.v[1][2]*x%P)%P; cout<<(res%P+P)%P<<endl; } else { X.clear();X.n=X.m=3;X.v[1][1]=X.v[2][2]=X.v[3][3]=1; for(t=1;t!=p;t=next[t]) if(N>=len[t]) { X=B*power(A,len[t])*X; N-=len[t]; } else break; LL y=(X.v[1][2]+X.v[1][3])%P,x=(X.v[2][2]+X.v[2][3])%P; Y.n=Y.m=2; Y.v[1][1]=1;Y.v[1][2]=1; Y.v[2][1]=1;Y.v[2][2]=0; Z=power(Y,N); LL res=(Z.v[1][1]*y%P+Z.v[1][2]*x%P)%P; cout<<(res%P+P)%P<<endl; } } return 0; }