将每一个重置为0的点作为一段，那么它会导致后面为以x x为开头的斐波拿起数列的东西，那么设这一段是以x为开头，要快速转移到下一段，就可以解决这道题目
为了转移，我们要处理出下面的东西：1.求出x关于模k的逆元，也就是找到这个0原来的值，那么x*上一个数就是下一段的开头；2.通过这个值反推出这一段的长度（因为我们要求出第n个数），并通过矩阵乘法求出上一个值
当(x,k)不等于1，那么就没有逆元，也就是说不会出现特殊情况，直接矩乘即可
当(x,k)=1，通过exgcd求出逆元后，由于斐波那契数列关于模k的循环节不超过6k，预处理出每一个i满足$i\equiv f[j](mod\ k)$的最小的j即可反推出长度
当然由于n过于大，有可能要经过很多个这样的东西，但由于这样的值只有k个，因此最终会形成循环，我们只需要在循环中快速查找即可
主要思路就是这样，实现起来要注意细节（比如答案不是对k取模而是对k）和实现的方法（比如特殊的转移也可以用矩阵来转移）
1 #include<bits/stdc++.h>
2 using namespace std;
3 #define N 1000005
4 struct ji{
5 int a[3][3];
6 }s,zy1,zy2,ans;
7 int k,p,fi,ne,vis[N],las[N];
8 long long n,l[N];
9 ji cheng(ji a,ji b){
10 ji c;
11 memset(c.a,0,sizeof(c.a));
12 for(int i=0;i<3;i++)
13 for(int j=0;j<3;j++)
14 for(int k=0;k<3;k++)
15 c.a[i][j]=(c.a[i][j]+1LL*a.a[i][k]*b.a[k][j])%p;
16 return c;
17 }
18 void ksm(long long n){
19 if (!n)return;
20 ji s=zy1;
21 while (n){
22 if (n&1)ans=cheng(ans,s);
23 s=cheng(s,s);
24 n/=2;
25 }
26 }
27 int exgcd(int a,int b,int &x,int &y){
28 if (!b){
29 x=1;
30 y=0;
31 return a;
32 }
33 int t=exgcd(b,a%b,y,x);
34 y-=a/b*x;
35 return t;
36 }
37 int main(){
38 scanf("%lld%d%d",&n,&k,&p);
39 ans.a[0][0]=ans.a[1][1]=ans.a[2][2]=1;
40 s=ans;
41 zy1.a[0][1]=zy1.a[1][0]=zy1.a[1][1]=zy1.a[2][2]=1;
42 zy2=zy1;
43 zy2.a[2][0]=zy2.a[2][1]=p-1;
44 int a=1,b=1;
45 for(int i=3;;i++){
46 int c=(a+b)%k;
47 if (!vis[c]){
48 vis[c]=i;
49 las[c]=b;
50 }
51 if ((!c)&&(b==1))break;
52 a=b;
53 b=c;
54 }
55 fi=1;
56 int flag=0;
57 while (1){
58 if (exgcd(fi,k,a,b)>1)break;
59 a=(a%k+k)%k;
60 if (n<vis[a])break;
61 n-=vis[a];
62 ksm(vis[a]-1);
63 ans=cheng(ans,zy2);
64 ne=1LL*fi*las[a]%k;
65 if ((flag<2)&&(l[ne])){
66 flag++;
67 if (flag<2)swap(ans,s);
68 else{
69 swap(ans,s);
70 swap(s,zy1);
71 ksm(n/(l[ne]-n)+1);
72 n%=l[ne]-n;
73 swap(s,zy1);
74 }
75 memset(l,0,sizeof(l));
76 }
77 l[fi=ne]=n;
78 }
79 ksm(n);
80 printf("%d",(ans.a[1][0]+ans.a[2][0])%p);
81 }