[Codeforces] 1182E
Product Oriented Recurrence
矩陣好難 :(
題敘
對於 $x \geq 4$，$f_n = c^{2n-6} f_{n-1} f_{n-2} f_{n-3}$。給定 $n, f_1, f_2, f_3, c$，求 $f_n \mod 10^9 + 7$。
$(4 \leq n \leq 10^{18}, 1 \leq f_1, f_2, f_3, c \leq 10^9)$
想法
TLE
用模仿費式數列 DP 的方法做的話……總複雜度 $\mathcal{O}(n)$， 看一下值域，感覺就是會吃爆 TLE……
快速冪
這裡要用到一個技巧：矩陣快速冪。
把原本的式子拆開，可以分成兩個部份解決：
先令 $a_n, b_n, c_n, p_n$ 代表 $f_n = c^{p_n} f_1^{a_n} f_2^{b_n} f_3^{c_n}$。
解決後半（$f_1^{a_n} f_2^{b_n} f_3^{c_n}$）
對於這個部分，有：
$$ \begin{cases} a_n = a_{n-1} + a_{n-2} + a_{n-3} \\ b_n = b_{n-1} + b_{n-2} + b_{n-3} \\ c_n = c_{n-1} + c_{n-2} + c_{n-3} \end{cases} $$所以可以用轉移矩陣來做這件事：
$$ \begin{bmatrix} {1} & {1} & {1} \\ {1} & {0} & {0} \\ {0} & {1} & {0} \end{bmatrix} \begin{bmatrix} {a_{n-1}} \\ {a_{n-2}} \\ {a_{n-3}} \end{bmatrix} = \begin{bmatrix} {a_{n-1} + a_{n-2} + a_{n-3}} \\ {a_{n-1}} \\ {a_{n-2}} \end{bmatrix} = \begin{bmatrix} {a_{n}} \\ {a_{n-1}} \\ {a_{n-2}} \end{bmatrix} $$結果：我們可以發現這三個共用一個轉移式，只要把左邊的矩陣用快速冪的方式，
就可以 $\mathcal{O}(\log n)$ 內求得 $a_n, b_n, c_n$。
然而，這個方法有溢位的風險，
實作上可以每次做完矩陣乘法 mod $10^9 + 6$，
原因是因為費馬小定理：
再透過一次快速冪，我們可以在 $\mathcal{O}(\log n)$ 內得到 $f_{n-1} f_{n-2} f_{n-3}$ 的部分，
而 $c^{2n-6}$ 呢？ 當然也可以！
解決前半（$c^{p_n}$）
先列出他的轉移式：
$$p_n = 2n-6 + p_{n-1} + p_{n-2} + p_{n-3}$$和前面不一樣的是，轉移式的前面多了變數，
在轉移矩陣轉移的時候，我們要同時維護$2n-6$，
可是矩陣好像不能每次 $+2$，每次 $+2$……嗎？
在這個部分，可以增開一維，放一個常數 $2$ 進去，
常數本身也很好維護，所以轉移矩陣像這樣：
結果記得隨時 mod，不然會溢位，
再次利用快速冪求得 $c^{p_n}$，複雜度 $\mathcal{O}(\log n)$。
結果
總複雜度 $\mathcal{O}(\log n)$。
AC Code
快速冪
寫得稍微有點長，不過應該蠻好看懂的（吧？）
| |