概要
大体公式解説と同じですが， $O(N\log^2N)$ ということで一応書きます．
いろんなところで多項式だけではなく Laurent 多項式が現れることに注意してください．
解法
次に帰着されます．ここまでは公式解説を見てください．
- $f(x) = x^{-1}+(N-3)+x$ とおく．
- $2N-1$ 次多項式 $B(x) = \sum b_ix^i$, $C(x) = \sum c_ix^i$ が与えられる．
- $S=0,1,\ldots,N$ に対して，$b(x)r(x)^S = \sum a_ix^i$ とするとき $\sum a_{i\bmod 2N}c_i$ を求めよ．
まず $\bmod 2N$ 要素が面倒なので処理します．$b$ の項の次数は $[0, 2N)$ したがって $b(x)r(x)^{S}$ の次数は $[-N,3N)$ におさまります．よって $c$ を周期 $2N$ に拡張して $[-N,3N)$ までを取り出したものを改めて $C(x)$ とすれば，求めるべきは単に $\sum a_ic_i$ となります．
$C$ を reverse しておくと，次に帰着できます：
各 $S$ に対して $[x^0]B(x)C(x)(x^{-1}+(N-3)+x)^S$ を求めよ．
$B,C$ の積を $f$ として $[x^0]B(x)C(x)(x^{-1}+(N-3)+x)^S$ を求めるという形です．これは分割統治で $O(N\log^2N)$ 時間で処理できます．
具体的には，$L\leq S < R$ と Laurent 多項式 $F$ に対して $[x^0]F(x)(x^{-1}+(N-3)+x)^{S-L}$ 答を計算する関数 $calc(F, L, R)$ を次のように設計します．
- $F$ を計算に必要な部分に制限する（$-n$ 次よりも下の項や $n$ 次よりも上の項は捨てる）
- $R=L+1$ なら答を出力して終了．そうでないとき $M=(L+R)/2$ として，$calc(F, L, M)$ および $calc(Fr^{M-L}, M, R)$ を呼ぶ．
$r^{M-L}$ の計算が必要になりますが，これは例えば $calc(F, L, R)$ の返り値として $r^{R-L}$ を返す機能を持たせればよいです．
各段階で $F$ を制限していることから大きさ $n$ の区間での計算量が $O(n\log n)$ になって，全体として $O(N\log^2N)$ 時間で答が計算できます．
