公式解説の解法2に近い発想に基づき、\(O(KM+\sqrt{N}\log N+p)\) 解法を解説します。
以下、等式は全て \(\bmod p\) で考えているものとします。

\(B_{K,i}\) に対して、\(K\) に関する帰納法により

\[B_{K,i} = \sum_{j=0}^{N-K} A_{i+j} \binom{N-K}{j}\]

という式が得られます。\(A\) が連長圧縮された形で与えられていることを用い、\(A_{i+j}\) の値が一定である区間をまとめることで、

\[B_{K,i} = \sum_{j=1}^{M} a_{j} \sum_{k\in I_{i,j}} \binom{N-K}{k}\]

のような形で表すことができます。ここで \(I_{i,j}\) は区間になります。

\(O(M)\) の前処理の下、区間 \(I_{i,j}\) を求めることは明らかに \(O(1)\) でできるので、二項係数 \(\binom{N-K}{k}\) の区間和を \(O(1)\) で求めることができれば、各 \(i\) に対して \(B_{K,i}\) を \(O(M)\) で求めることができ、全体で \(O(MK)\) で問題を解くことができます。

二項係数の区間和

次を示します：
\(N\) が与えられたとき、\(O(\sqrt{N}\log N+p)\) の前計算の下、区間和 \(\binom{N}{0}+\ldots+\binom{N}{R-1}\) をクエリあたり \(O(1)\) で求めることができる。

平方分割によります。以下では除算は整数に切り捨てるものとし、\(\%\) は(最小非負)剰余を取る演算とします。

\(O(p)\) の前計算により、\(n.r<p\) に対する \(\binom{n}{r}\) は \(O(1)\) で求めることができます。これを用いることで、Lucas の定理により任意の \(\binom{n}{r}\) は \(O(\log n)\) で求めることができます。

\(D\) を \(\sqrt{N}\) を超える最小の \(p\) ベキとします。\(k< D\) の範囲に対して \(\binom{N/D}{k},\binom{N\%D}{k}\) を \(O(\sqrt{N}\log N)\) 時間かけて愚直に計算します（再帰的に計算することで \(O(\sqrt{N})\) で求めることもできます）。同時に、それぞれの累積和も求めておきます。

Lucas の定理から \(\binom{N}{k}=\binom{N/D}{k/D}\binom{N\%D}{k\%D}\) が成り立つので、

\[ \begin{aligned} \sum_{k=0}^{R-1} \binom{N}{k}&=\sum_{q=0}^{R/D-1}\left(\binom{N/D}{q}\sum_{r=0}^{D-1}\binom{N\%D}{r}\right)+\sum_{r=0}^{R\%D-1} \binom{N/D}{R/D}\binom{N\%D}{r}\\ &=\sum_{q=0}^{R/D-1}\binom{N/D}{q}\sum_{r=0}^{D-1}\binom{N\%D}{r}+\binom{N/D}{R/D}\sum_{r=0}^{R\%D-1} \binom{N\%D}{r} \end{aligned} \]

が成り立ち、前計算したものたちを使って \(O(1)\) で求めることができるとわかりました。

実装例(C) (800ms)

上位の桁と下位の桁に分けるという発想に基づく解法を使う類題
No.262 面白くないビットすごろく yukicoder