题解：CF2033F Kosuke's Sloth

千早爱音 · 2024-11-08 09:22:00 · 题解

前置知识：https://www.luogu.com.cn/problem/solution/SP13419

有了上题的结论，我们不难算出斐波那契数列的最小周期，然后直接乘 n 即可。

然而我们发现如果直接提交，这个代码连样例都过不去。

原因在一个数模 p 等于 0 并不能代表其下一位一定模 p 后为 1 ，不符合最小周期的定义。

于是我们发现这个周期一定是最小周期的某个约数，这里由于上述结论循环节不超过 6p 所以直接枚举出所有约数之后判断其约数对应的位置是否为 0 ，当然也可以用更优秀的实现，比如矩阵快速幂等等，此处不再详述。

不优化时的时间复杂度不变，为 \mathcal{O}(Tn) ，采取优化之后可以进一步优化到 \mathcal{O}(Tn^\frac{1}{4}\log{n}) ，来自质因数分解和矩阵快速幂的时间复杂度，因为实现太复杂所以没写。

code