题解
模拟能拿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$，则可以发现：
- 每一段的开头两个数都是相同的两个数，并且正好就是前面那一个段的最后一个非$0$数。同时只有除$k$和$0$以外的$k-1$种数，所以最多在不超过$k$段的情况下就会出现循环。（假设这个循环是存在的话。）
- 对于某一段而言，这一段都相当于一段小的斐波那契数列。
比如说某一段的开头是$x$，那么这一段就是
$x,x,2x,3x,5x,8x,…$
换言之，这一段的第$i$个数就是$fib[i]\cdot x$。
如果这一段有长度，那么设长度是$Len$，则$fib[Len]\cdot x \mod k=1$.
这个时候就是我们要减掉$1$的时候。
有了以上的推导，我们不难得出具体算法：
- 根据$fib[Len]\cdot x \mod k=1$求出$fib[Len]$
- 反推出$Len$
- 求出下一段的开头，也就是$fib[Len-1]\cdot x$，转回第1步
第1步里头，不难发现$fib[Len]$就是$x^{-1}(mod\quad k)$，所以如果逆元都不存在的话这就成了裸题。
否则，算出逆元。
第2步，预处理出对于每个$i$，$fib[Len]=i$的最小$Len$。如果是不存在，那么也变成了矩阵乘法裸题。
但是可能这个$Len$很大啊？
有2个方法：
- 估计一下$fib \mod k$的循环节长度，直接算
- 数学证明。
vfk大佬的博客上有证明，我不会证，只知道了结论：$fib \mod k$的循环节是以$0,1,1$为开头的，且长度不超过$6000$。
就直接算了。
第3步，由于直接模拟可能超时，所以要用矩阵快速幂。一个数减掉$1$是一个很好写的矩阵，这里就不列了，有兴趣的看代码吧。
剩下的细节还挺好处理的。边算边记录答案即可。
1 |
|
v1.5.2