1. 题目

传送门= ̄ω ̄=

2. 题解

居然比赛的时候想出来正解了。

设广义斐波那契数列:$A$,第$i$项为$A_i$

设“狭义”(一般)斐波那契:$Fib$,第$i$项为$Fib_i$

则:$A_i=A_1\times Fib_{i-2}+A_2\times Fib_{i-1}$

那么题目要求:$A_k=m(MOD\ p)$

即:$A_1\times Fib_{k-2}+A_2\times Fib_{k-1}=m(MOD\ p)$

其中$A_1,k,m,p$均已知,只有$A_2$未知。

设$G=A_1\times Fib_{k-2}$

则:$G+A_2\times Fib_{k-1}=m(MOD\ p)$

$A_2\times Fib_{k-1}=m-G(MOD\ p)$

显然这就是个线性同余方程了,求出最小整数解然后求解的个数即可。

其中计算$Fib_{k-1},Fib_{k-2}$可以$O(log_2k)$的复杂度求出。

总复杂度$O(T\times log_2k)$

求斐波那契数列我没用矩阵乘法,用了这个:传送门= ̄ω ̄=,可以去参考一下~

代码(有点凌乱):