【TOI2019 二模 pA】吠市數列
題目敘述 給定一質數$p$和$a_0$, $a_1$，定義數列$\{a\}$滿足遞迴式 $$a_n=a_{n-1}+a_{n-2}+1,\, \forall n \ge 2$$ 現在我們知道$x$, $a_x$, $y$, $a_y$, $k$，求$a_k$。若無解輸出$-1$，若有超過一解輸出$-2$ $x$, $y$, $k$都在long long範圍內，$p$在int範圍內 作法 首先根據簡單的運算我們有 $$a_n=F_{n-2}a_0+F_{n-1}a_1+F_{n}-1$$ 其中$\{F\}$為費波那契數列（$F_0=F_1=1$），且$F_{-1}=0$, $F_{-2}=1$ 令$a=F_{x-2}\%p$, $b=F_{x-1}\%p$, $c=F_{y-2}\%p$, $d=F_{y-1}\%p$, $e=F_{k-2}\%p$, $f=F_{k-1}\%p$ （用矩陣快速冪等方法求得） 我們有 $$ag_0+bg_1 \equiv a_x -(F_{x}-1) \pmod p$$ $$cg_0+dg_1 \equiv a_y -(F_{y}-1) \pmod p$$ 然後想要知道 $$eg_0+fg_1$$ 是多少 二元一次聯立方程式式國中課程內容，但如果套用到模運算下會很麻煩，尤其我們並不是真的要求$g_0$, $g_1$，而只要$eg_0+fg_1$。以下提供一個暴力分case的方法，雖然應該存在簡短的方式，但這種直覺的作法應該不容易漏case。 首先有個簡單的Lemma説對於所有質數$p$，不存在$i$使得$F_i$, $F_{i+1}$都是$p$的倍數，證明會在後面補。所以不會發生$a=0$且$b=0$，也不會發生$c=0$且$d=0$的情況。接下來就是分類了： $\mathbf{a=0}$ 首先我們可以用$bg_1 \equiv a_x -(F_{x}-1)$求出$g_1$，然後代入第二條式子得到 $$cg_0 \equiv a_y -(F_{y}-1)-dg_1 \pmod p$$ 若$c=0$ $a_y -(F_{y}-1)-dg_1 \equiv 0$，則無限多組解 否則無解 若$c\neq 0$，直接計算出$g_0$
