NC17631. [NOI2011]兔农
描述
输入描述
输入一行，包含三个正整数n, k, p。
输出描述
输出一行，包含一个整数，表示栋栋第n个月的兔子对数除p的余数。
示例1
输入:
6 7 100
输出:
7
C++14(g++5.4) 解法, 执行用时: 319ms, 内存消耗: 42460K, 提交时间: 2020-05-05 19:42:10
#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
long long n,k,p,vis[N],f[N*6],ni[N],len[N];
bool ext[N];
void exgcd(long long a,long long b,long long&x,long long &y,long long &d)
{
if(b==0)
{
d=a;
x=1;
y=0;
}
else
{
exgcd(b,a%b,y,x,d);
y-=x*(a/b);
}
}
inline long long inv(long long a,long long mod)
{
long long d,x,y;
exgcd(a,mod,x,y,d);
return d==1?(x+mod)%mod:-1;
}
struct marx
{
long long m[4][4];
marx(){}
inline long long *operator [](long long x){return m[x];}
inline void clear(){memset(m,0,sizeof(m));}
marx operator * (const marx &b) const
{
marx c;c.clear();
for(int k=1;k<=3;k++)
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++)
c.m[i][j]=(c.m[i][j]%p+m[i][k]%p*b.m[k][j]%p)%p;
return c;
}
};
marx mat[N],A,B,C,ans;
inline marx poww(marx x,long long len)
{
marx ret;
ret.clear();
ret[1][1]=ret[2][2]=ret[3][3]=1;
while(len)
{
if(len&1) ret=ret*x;
len>>=1;
x=x*x;
}
return ret;
}
int main()
{
cin>>n>>k>>p;
f[1]=f[2]=1;
for(int i=3; ;i++)
{
f[i]=(f[i-1]+f[i-2])%k;
if(!vis[f[i]]) vis[f[i]]=i;
if(f[i]==f[i-1]&&f[i]==1) break;
}
A[1][1]=A[1][2]=A[2][1]=A[3][3]=1;
B[1][1]=B[2][2]=B[3][3]=1;
B[3][1]=-1;
ans[1][2]=ans[1][3]=1;
long long x=1;
bool flag=0;
while(n)
{
if(!ni[x]) ni[x]=inv(x,k);
if(ni[x]==-1)
{
ans=ans*poww(A,n);
n=0;
}
else if(!ext[x]||flag)
{
ext[x]=1;
if(!vis[ni[x]]) ans=ans*poww(A,n),n=0;
else
{
len[x]=vis[ni[x]];
if(n>=len[x])
{
n-=len[x];
mat[x]=poww(A,len[x])*B;
ans=ans*mat[x];
x=x*f[len[x]-1]%k;
}
else
{
ans=ans*poww(A,n);
n=0;
}
}
}
else
{
long long cnt=0;
C.clear();
C[1][1]=C[2][2]=C[3][3]=1;
for(long long i=x*f[len[x]-1]%k;i!=x;i=i*f[len[i]-1]%k)
cnt+=len[i],C=C*mat[i];
cnt+=len[x];
C=mat[x]*C;
ans=ans*poww(C,n/cnt);
n%=cnt;
flag=1;
}
}
cout<<(ans[1][1]%p+p)%p<<endl;
return 0;
}
C++(clang++ 11.0.1) 解法, 执行用时: 118ms, 内存消耗: 42448K, 提交时间: 2022-09-04 18:53:21
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;
const int N=1000010;
LL n,k,p,vis[N],f[N*6],ni[N],len[N];
bool ext[N];
void exgcd(LL a,LL b,LL&x,LL &y,LL &d){
if(b==0)d=a,x=1,y=0;
else exgcd(b,a%b,y,x,d),y-=x*(a/b);
}
inline LL inv(LL a,LL mod){
LL d,x,y;exgcd(a,mod,x,y,d);
return d==1?(x+mod)%mod:-1;
}
struct marx{
LL m[4][4];
marx(){}
inline LL *operator [](LL x){return m[x];}
inline void clear(){memset(m,0,sizeof(m));}
marx operator * (const marx &b) const{
marx c;c.clear();
for(int k=1;k<=3;k++)for(int i=1;i<=3;i++)for(int j=1;j<=3;j++)c.m[i][j]=(c.m[i][j]%p+m[i][k]%p*b.m[k][j]%p)%p;
return c;
}
}mat[N],A,B,C,ans;
inline marx poww(marx x,LL len){
marx ret;ret.clear();
ret[1][1]=ret[2][2]=ret[3][3]=1;
while(len){
if(len&1)ret=ret*x;
len>>=1;x=x*x;
}
return ret;
}
int main(){
scanf("%lld%lld%lld",&n,&k,&p);
f[1]=f[2]=1;
for(int i=3;;i++){
f[i]=(f[i-1]+f[i-2])%k;
if(!vis[f[i]])vis[f[i]]=i;
if(f[i]==f[i-1]&&f[i]==1)break;
}
A[1][1]=A[1][2]=A[2][1]=A[3][3]=1;
B[1][1]=B[2][2]=B[3][3]=1,B[3][1]=-1;
ans[1][2]=ans[1][3]=1;
LL x=1;bool flag=0;
while(n){
if(!ni[x])ni[x]=inv(x,k);
if(ni[x]==-1)ans=ans*poww(A,n),n=0;
else{
if(!ext[x]||flag){
ext[x]=1;
if(!vis[ni[x]])ans=ans*poww(A,n),n=0;
else{
len[x]=vis[ni[x]];
if(n>=len[x]){
n-=len[x];
mat[x]=poww(A,len[x])*B;
ans=ans*mat[x],x=x*f[len[x]-1]%k;
}
else ans=ans*poww(A,n),n=0;
}
}else{
LL cnt=0;
C.clear();C[1][1]=C[2][2]=C[3][3]=1;
for(LL i=x*f[len[x]-1]%k;i!=x;i=i*f[len[i]-1]%k)
cnt+=len[i],C=C*mat[i];
cnt+=len[x],C=mat[x]*C;
ans=ans*poww(C,n/cnt);
n%=cnt,flag=1;
}
}
}
printf("%lld",(ans[1][1]%p+p)%p);
return 0;
}