給定兩個長度為 $N$ 的非負整數序列 $a_0,a_1,\cdots ,a_{N-1}$ 和 $c_0,c_1,\cdots ,c_{N-1}$ 以及一個正整數 $K$ ，定義數列 $a$ 的第 $j$ 項 $a_j=\sum _{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 _{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(\mathrm{mod}{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(\mathrm{mod}{x}^{2a})\Rightarrow D+A\cdot C\equiv 0(\mathrm{mod}{x}^a)\Rightarrow -B_{k}D\equiv C(\mathrm{mod}{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(\mathrm{mod}{x}^{n-m+1})$ 成立，把餘數翻到高次項去巧妙的處理掉了！

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

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