NOI2011 兔农

发表于 | 分类于 ， |
字数统计: 1,679 字

题目链接

题解

模拟能拿75分。
题目肯定是和斐波那契数列有关，但有关在哪里呢？
由于有取模，所以我们看看有没有什么和循环有关的性质。
我们设$fib[i]$为斐波那契数列的第$i$项，而设$F[i]$为该数列的第i项。
把$k=7$作为例子，观察$F[i]$对$k$取模的序列：
$1,1,2,3,5,0, $
$5,5,3,0, $
$3,3,6,2,0,$
$2,2,4,6,3,2,5,0,5,5,3,0,$
（之所以这一段前面的$0$不算是一段的结尾，是因为这个$0$不是由于减了一个$1$而产生的）
$3,3,6,2,0,…$
设$fib[0]=0$，则可以发现：

  1. 每一段的开头两个数都是相同的两个数，并且正好就是前面那一个段的最后一个非$0$数。同时只有除$k$和$0$以外的$k-1$种数，所以最多在不超过$k$段的情况下就会出现循环。（假设这个循环是存在的话。）
  2. 对于某一段而言，这一段都相当于一段小的斐波那契数列。
    比如说某一段的开头是$x$，那么这一段就是
    $x,x,2x,3x,5x,8x,…$
    换言之，这一段的第$i$个数就是$fib[i]\cdot x$。
    如果这一段有长度，那么设长度是$Len$，则$fib[Len]\cdot x \mod k=1$.
    这个时候就是我们要减掉$1$的时候。

有了以上的推导，我们不难得出具体算法：

  1. 根据$fib[Len]\cdot x \mod k=1$求出$fib[Len]$
  2. 反推出$Len$
  3. 求出下一段的开头，也就是$fib[Len-1]\cdot x$，转回第1步

第1步里头，不难发现$fib[Len]$就是$x^{-1}(mod\quad k)$，所以如果逆元都不存在的话这就成了裸题。
否则，算出逆元。
第2步，预处理出对于每个$i$，$fib[Len]=i$的最小$Len$。如果是不存在，那么也变成了矩阵乘法裸题。
但是可能这个$Len$很大啊？
有2个方法：

  1. 估计一下$fib \mod k$的循环节长度，直接算
  2. 数学证明。
    vfk大佬的博客上有证明，我不会证，只知道了结论：$fib \mod k$的循环节是以$0,1,1$为开头的，且长度不超过$6000$。
    就直接算了。

第3步，由于直接模拟可能超时，所以要用矩阵快速幂。一个数减掉$1$是一个很好写的矩阵，这里就不列了，有兴趣的看代码吧。

剩下的细节还挺好处理的。边算边记录答案即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f=1,x=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}    
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return f*x; 
}
ll n,k,p,ans;
ll minlen[1000005],block[1000005][3],vis[1000005]={0},top=0;
ll sum[1000005]={0};
ll FIB[3][3]={
    {0,1,0},
    {1,1,0},
    {0,0,1}
},MINUS[3][3]={
    {1,0,0},
    {0,1,0},
    {0,-1,1}
};
//vis 总长度为什么时开头变成了i 
// block保存段长信息 
struct Mat{
    ll dat[3][3];
    int r,c;
    Mat(){
        memset(dat,0,sizeof(dat));
    }
};
Mat Minus,Fib;
Mat mul(Mat &a,Mat &b,ll Mod){
    Mat newed;
    newed.r=a.r,newed.c=b.c;
    int i,j,k;ll t;
    for(i=0;i<a.r;i++)
        for(j=0;j<b.c;j++){
            for(t=0,k=0;k<a.c;k++)t+=(a.dat[i][k])*(b.dat[k][j]),t%=Mod;
            newed.dat[i][j]=t%Mod;
        }
    return newed;
}
Mat Pow(Mat a,ll p,ll Mod){
    Mat E;E.r=E.c=a.c;
    int i,j;
    for(i=0;i<a.c;i++)
        E.dat[i][i]=1;
    while(p){
        if(p&1)E=mul(E,a,Mod);
        a=mul(a,a,Mod),p>>=1;
    }
    return E;
}
ll extgcd(ll a,ll b,ll &x,ll &y){
    if(!b){
        x=1,y=0;
        return a;
    }
    ll d=extgcd(b,a%b,y,x);
    y-=(a/b)*x;
    return d;
}
void setfib(Mat &mat){
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            mat.dat[i][j]=FIB[i][j];
    mat.r=mat.c=3;
}
void setminus(Mat &mat){
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            mat.dat[i][j]=MINUS[i][j];
    mat.r=mat.c=3;
}
void init(){
    scanf("%lld%lld%lld",&n,&k,&p);
    memset(minlen,-1,sizeof(minlen));
    memset(vis,-1,sizeof(vis));
    ll fib1=1,fib2=1,fib3,t;
    for(ll i=3;i<=6*k;i++){
        fib3=(fib1+fib2),t=fib3%k;
        //printf("\t  %lld %lld %lld\n",fib1,fib2,t);
        if(t==1&&fib2==1&&fib1==0)break;
        if(minlen[t]<0)minlen[t]=i;
        fib1=fib2,fib2=t;
    }
    MINUS[2][1]=p-1;
    //计算对应的Len 
    setfib(Fib),setminus(Minus);
}
void solve(){
    ll x=1,dx,dy,d,len;
    ll cyc=-1;
    Mat Ori,Plu,res;
    Ori.r=1,Ori.c=3;
    Ori.dat[0][0]=Ori.dat[0][2]=1,
    Ori.dat[0][1]=0;
    for(;;){
        d=extgcd(x,k,dx,dy);
        //ax+bk=1
        if(d!=1)
            break;
        else{
            //逆元存在
            dx=(dx+k)%k,len=minlen[dx];
            if(len==-1)//不存在对应的
                break;
            block[top][0]=x,block[top][1]=len;
            Plu=Pow(Fib,len-1,k);
            res=mul(Ori,Plu,k);
            //求出fib[len-1]
            block[top++][2]=(x*res.dat[0][1])%k;
            x=block[top-1][2];
            sum[top]=sum[top-1]+len;
            if(vis[x]>=0){
                //说明top-1的后面和cyc是一样的 
                cyc=vis[x]+1;
                break;
            }
            vis[x]=top-1;
        } 
    }
    if(cyc==-1){
        //没有最终的循环节，就变成矩阵乘法裸题 
        for(ll i=0;i<top&&n;i++){
            len=block[i][1];
            Plu=Pow(Fib,min(n,len),p);
            Ori=mul(Ori,Plu,p);
            if(n<len){
                n=0;break;
            }
            n-=len;
            Ori=mul(Ori,Minus,p);
        }
        if(n)
            Plu=Pow(Fib,n,p),
            Ori=mul(Ori,Plu,p);
        ans=Ori.dat[0][1];
    }else{
        for(ll i=0;i<cyc&&n;i++){
            len=block[i][1];
            Plu=Pow(Fib,min(n,len),p);
            Ori=mul(Ori,Plu,p);
            if(n<len){
                n=0;break;
            }
            n-=len;
            Ori=mul(Ori,Minus,p);
        }
        if(!n){
            ans=Ori.dat[0][1];goto build_ans;
        }
        d=n/(sum[top]-sum[cyc]),n%=(sum[top]-sum[cyc]);
        if(d){
            //至少存在一个循环节 
            for(ll i=0;i<3;i++)
                for(ll j=0;j<3;j++)
                    Plu.dat[i][j]=(i==j)?1:0;
            Plu.r=Plu.c=3;
            for(ll i=cyc;i<top;i++)
            	res=Pow(Fib,block[i][1],p),res=mul(res,Minus,p),Plu=mul(Plu,res,p);
            Plu=Pow(Plu,d,p),Ori=mul(Ori,Plu,p);
        }
        for(ll i=cyc;i<top&&n;i++){
            len=block[i][1];
            Plu=Pow(Fib,min(n,len),p);
            Ori=mul(Ori,Plu,p);
            if(n<len){
                n=0;break;
            }
            n-=len;
            Ori=mul(Ori,Minus,p);
        }
        ans=Ori.dat[0][1];
    }
    build_ans:
    printf("%lld\n",ans);
}
int main(){
    init();
    solve();
    return 0;
}