這邊先警告一下 這絕不是可以輕鬆寫的題目
我的程式碼超過10KB 有300多行

以下用$m, k, n$分別代替原題的$M, K, N$
大家有沒有發現 這題只要算出$x^{n-1}$除以$f(x):=x^k-c_1x^{k-1}-c_2x^{k-2}-\ldots-c_{k-1}x-c_k$的餘式就結束了?

考慮$V = (從\mathbb{Z}_{\geq 1}到\mathbb{C}的函數集合)$ 令$u, v \in V, c \in \mathbb{C}$ 我們定義$V$裡的加法和係數積如下

1. $(u+v)(i) := u(i) + v(i)$ for each $i \in \mathbb{Z}_{\geq 1}$
2. $(cu)(i) := cu(i)$ for each $i \in \mathbb{Z}_{\geq 1}$

不難發現在這樣的定義下$V$是個$\mathbb{C}$-vector space

接著 引入左移算子$L: V \to V$
對於所有的$v \in V$ 定義$(Lv)(i) = v(i+1)$ for each $i \in \mathbb{Z}_{\geq 1}$
我們可以發現$L$是個線性算子

回到我們的問題
設$v \in V$ 並令$v(i)=a_i$ for each $1\leq i\leq k$
對於$i>k$ 遞迴定義
$$v(i) = c_1 v(i-1) + c_2 v(i-2) + \ldots + c_k v(i-k)$$
這樣一來 我們就有
$$L^k v = c_1 L^{k-1} v + c_2 L^{k-2} v + \ldots + c_k v$$
因為$L$是線性的 上式可以改寫成
$$(L^k - c_1 L^{k-1} - c_2 L^{k-2} - \ldots - c_k) v = 0$$
亦即
$$(f(L))v = 0$$

注意原本問題的答案就是$v(n)$除以$m$的餘數 因為$v(n) = (L^{n-1}v)(1)$ 我們將$L^{n-1}$除以$f(L)$ 得到
$$L^{n-1} = f(L)q(L) + r(L)$$
這樣一來 就有
$$v(n) = (L^{n-1}v)(1) = ((f(L)q(L) + r(L))v)(1) = (r(L)v)(1)$$
令$r(L) = r_0 + r_1 L + \ldots + r_{k-1} L^{k-1}$ 則有
$$
\begin{split}
(r(L)v)(1) &= ((r_0 + r_1 L + \ldots + r_{k-1} L^{k-1})v)(1)\\
&= r_0 v(1) + r_1 (Lv)(1) + \ldots + r_{k-1} (L^{k-1}v)(1)\\
&= r_0 v(1) + r_1 v(2) + \ldots + r_{k-1}v(k)\\
&= r_0 a_1 + r_1a_2 + \ldots + r_{k-1}a_k
\end{split}
$$

那麼要怎麼算$r$呢?
回想一下 設$b \in \mathbb{Z}_{\geq 1}$ 要計算$b^n$ mod $m$ 可以用divide and conquer做到$O(\log n)$的時間複雜度
想計算$x^{n-1}$ mod $f(x)$ 採取同樣的方法 就可以用$O(\log n)$次乘法與取餘式操作算出
多項式的乘除法都可以做到$O(d \log d)$ 其中$d$是多項式的次數 這邊$d = O(k)$
因此整體的時間複雜度就是$O(k \log k \log n)$ 感恩線代 讚嘆線代

關於多項式的乘法部分 有個地方要注意一下
因為這題的$m$很大 多項式相乘後係數可以破$10^{18}$
但不幸的是用double實作的FFT的精度只到$15$位有效數字
一種解決方式是先做一次FFT估計係數 再做一次NTT(number-theoretic transform)校正尾數
另一種解決方式是先做兩次NTT 再用CRT(Chinese remainder theorem)得到係數