給定兩個長度為 $N$ 的非負整數序列 $a_0, a_1, \cdots, a_{N-1}$ 和 $c_0, c_1, \cdots, c_{N-1}$ 以及一個正整數 $K$ ，定義數列 $a$ 的第 $j$ 項 $a_j = \sum \limits _ {i = 0} ^ {N-1} a_{j-N+i} \cdot c_{i}$，求 $a_K$ 。

最基礎的作法是透過 DP 在 $O(NK)$ 時間內得到解，再進階一點可以利用矩陣快速冪得到 $O(N^ 3 \log K)$ 的作法。不過這樣做只會拿到一分。不要緊張，這是一題閱讀測驗題，好好照著題目寫的做就可以拿到分數（吧）。

考慮通靈

考慮把 $a_K$ 用 $a_{K-1} \sim a_{K-N}$ 表示，再把留下來的 $a_{K-1}$ 們用 $a_{K-2} \sim a_{K-1-N}$ 表示，會發現過程長的超像多項式的長除法！

（出題者懶得寫算式，請自己拿紙筆用範測一試一下）

正確來說，如果我們計算 $x^ K$ 除以 $B(x) = x^ N - \sum \limits _ {i = 0} ^ {N-1} c_{i} x^ i$ 的餘式 $R(x)$，並拿 $R(x)$ 中 $x^ 0 \sim x^ {N-1}$ 項的係數與 $a_0 \sim a_{N-1}$ 一一相乘並加總，就會得到 $a_K$ 。

我們可以對 $x$ 這個多項式做模 $B(x)$ 的快速冪，並用 $O(N^ 2)$ 的時間實作多項式的乘法以及取餘式，那麼我們就可以在 $O(N^ 2 \log K)$ 的時間內做完快速線性遞迴！這個方法叫做 Kitamasa Method ，是個實作簡短但實用的演算法。

接下來，你可以選擇就這樣拿 20 分走，或繼續往下閱讀（推薦）……

快，還要更快！

早上上過卷積課的你應該要知道，多項式相乘可以在 $O(N \log N)$ 的時間完成，要是也能在 $O(N \log N)$ 時間內完成多項式的除法、取餘就好了！

還真的可以。

逆多項式

設 $A(x)$ 為一個 $N-1$ 次多項式，只要 $A(x)$ 的常數項非 0 ，我們就可以找到 $A(x)$ 在模 $x^ N$ 底下的逆多項式（有點像模逆元），也就是可以找的到 $A^ {-1}(x)$ 使得 $A(x) \cdot A^ {-1}(x) \equiv 1 \pmod {x^ N}$ 。至於要怎麼找呢？繼續考慮通靈。

我們先找到模 $x$ 底下 $A(x)$ 的逆多項式。令它叫 $B_0$ 。

當我們有模 $x^ {2^ k}$ 底下的 $A(x)$ 的逆多項式 $B_k$ 後，我們想求得 $B_{k+1}$ ，最後只要取到 $2^ k \ge N$ 就可以了。要怎麼做這個倍增的過程呢？

我們先令 $a = 2^ k, B_{k+1} = B_k + x^ a \cdot C, A \cdot B_k = 1 + x^ a \cdot D$ 。很顯然的，$A \cdot B_{k+1} = 1 + x^ a \cdot D + A \cdot x^ a \cdot C$ ，而根據 $B_{k+1}$ 的定義， $1 + x^ a \cdot D + A \cdot x^ a \cdot C \equiv 1 \pmod {x^ {2a}} \Rightarrow D + A \cdot C \equiv 0 \pmod {x^ {a}} \Rightarrow -B_k D \equiv C \pmod {x^ {a}}$ 。

而 $B_k$ 已知， $D$ 可以用一個乘法在 $O(a \log a)$ 的時間內算出來，故也可以在 $O(a \log a)$ 時間內求出 $C$ 以及 $B_{k+1}$ ！整體時間複雜度是 $O(N \log N)$ 的。

除法

假設要計算 $A(x)$ 除以 $B(x)$ ，設商 $Q(x)$ 、餘 $R(x)$ ，可以得到 $A(x) = B(x) Q(x) + R(x)$ 。假設 $A$ 是 $n$ 次、 $B$ 是 $m$ 次多項式，且 $n \ge m$，則可得 $Q$ 是 $n - m$ 次的，而 $R$ 至多 $m-1$ 次。

考慮把 $A, B, Q$ 全部翻轉，變成 $A^ r = x^ n A(x^ {-1}), B^ r = x^ m B(x^ {-1}), Q^ r = x^ {n-m} Q(x^ {-1})$ ，可以發現 $A^ r \equiv B^ r Q^ r \pmod{x^ {n-m+1}}$ 成立，把餘數翻到高次項去巧妙的處理掉了！

我們已經會（應該吧）求 $B^ r$ 在模 $x^ {n-m+1}$ 底下的逆多項式了，我們就可以在 $O(n \log n)$ 時間求得 $Q^ r$ ，進一步求得 $Q, R$ ！

實作時要小心處理一些邊界狀況，例如 $R$ 是 0 多項式，或是倍增的邊界等等。希望大家都能看到這邊並寫出來，真的比理解卷積簡單很多啦 qwq