记录编号	603162	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	1374.[NOI 2011]兔农	最终得分	100
用户昵称	李奇文	是否通过	通过
代码语言	C++	运行时间	1.216 s
提交时间	2025-07-09 16:23:22	内存使用	11.68 MiB

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5,C=3;
int n,k,p,kcnt;
int f[6*N],len[N],fir[N],vis[N];
bool flag;
struct juzhen{
	int o[C+1][C+1];
	juzhen(){
		memset(o,0,sizeof(o));
	}
	juzhen operator*(const juzhen &x) const {
		juzhen res;
		for(int i=1;i<=C;i++){
			for(int j=1;j<=C;j++){
				for(int k=1;k<=C;k++){
					res.o[i][j]=(res.o[i][j]+o[i][k]*x.o[k][j]+p)%p;
				}
			}
		}
		return res;
	}
}mat,tr1,tr2,tr;
juzhen jzksm(juzhen a,int b){
	juzhen res;
	for(int i=1;i<=C;i++) res.o[i][i]=1;
	while(b){
		if(b&1){
			res=res*a;
		}
		a=a*a;
		b>>=1;
	}
	return res;
}
int exgcd(int a,int b,int &x,int &y){
	if(!b){
		x=1;
		y=0;
		return a;
	}
	int gcd=exgcd(b,a%b,x,y);
	int f=x;
	x=y;
	y=f-a/b*y;
	return gcd;
}
int gcd(int a,int b){
	return b==0?a:gcd(b,a%b);
}
int ny(int a,int P){
	if(gcd(a,P)!=1) return -1;
	int x,y;
	exgcd(a,P,x,y);
	return (x%P+P)%P;
}
signed main(){
	freopen("noi2011_rabbit.in","r",stdin);
	freopen("noi2011_rabbit.out","w",stdout);
	scanf("%lld%lld%lld",&n,&k,&p);
	if(n==1||n==2){
		cout<<1<<endl;
		return 0;
	}
	f[1]=f[2]=1;
	memset(len,999999,sizeof(len));
	for(int i=3;;i++){
		f[i]=(f[i-1]+f[i-2])%k;
		if(f[i]%k==1&&len[1]>1e18) len[1]=i;
		if(f[i]==1&&f[i-1]==1) break;
		int inv=ny(f[i],k);
		if(inv!=-1) len[inv%k]=min(len[inv%k],i);
	}
	int now=1,tot=0;
	while(1){
		fir[++kcnt]=now;
		vis[now]=kcnt;
		if(len[now]>1e18){
			for(int i=1;i<kcnt;i++) tot+=len[fir[i]];
			flag=1;
			break;
		}
		now=(now*f[len[now]-1])%k;
		if(vis[now]){
			for(int i=1;i<vis[now];i++) tot+=len[fir[i]];
			break;
		}
	}
	mat.o[1][1]=mat.o[1][3]=1;
	tr1.o[1][1] = tr1.o[1][2] = tr1.o[2][1] = tr1.o[3][3] = 1;
	tr2.o[1][1] = tr2.o[1][2] = tr2.o[2][1] = tr2.o[3][3] = 1;
	tr2.o[3][1] = -1;
	if(n<=tot){
		len[1]--;
		n--;
		for(int i=1;i<vis[now];i++){
			if(n>=len[fir[i]]){
				mat=mat*jzksm(tr1,len[fir[i]]-1)*tr2;
				n-=len[fir[i]];
			}else{
				mat=mat*jzksm(tr1,n);
				printf("%lld\n",mat.o[1][1]);
				return 0;
			}
		}
	}else{
		len[1]--;
		n-=tot;
		for(int i=1;i<vis[now];i++) mat=mat*jzksm(tr1,len[fir[i]]-1)*tr2;
		if(flag){
			mat=mat*jzksm(tr1,n);
			printf("%lld\n",mat.o[1][1]);
		}else{
			int ll=0;
			for(int i=1;i<=C;i++) tr.o[i][i]=1;
			for(int i=vis[now];i<=kcnt;i++){
				tr=tr*jzksm(tr1,len[fir[i]]-1)*tr2;
				ll+=len[fir[i]];
			}
			int tmp=n/ll;
			mat=mat*jzksm(tr,tmp);
			n=n-ll*tmp;
			for(int i=vis[now];i<=kcnt;i++){
				if(n>=len[fir[i]]){
					mat=mat*jzksm(tr1,len[fir[i]]-1)*tr2;
					n-=len[fir[i]];
				}else{
					mat=mat*jzksm(tr1,n);
					printf("%lld\n",mat.o[1][1]);
					return 0;
				}
			}
		}
	}
	return 0;
}