开了各种玩意才艹过去
看没有题解,就交了个(
很有趣的一道题
看到这种求数列的题就感觉是矩阵快速幂
接近于求个斐波拉契数列
但是中间会有转移方程不同的地方
很烦
那么我们就可以想到通过要减一的地方分段矩阵快速幂,那就可以解决这一个问题
很显然,斐波拉契在$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>
#pragma GCC optimize("2")
#pragma GCC optimize("3")
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#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");
}