\(M=1\) の場合を考えます。

\((1,2,\dots,N)\) をいくつかの連続部分列に分け、長さが \(2\) 以上のものは反転するかどうかを決め、その後並び替えることを考えます。

例えば、\((1,2,3,4,5,6)\) を \((1,2,3),(4),(5,6)\) に分け、\((1,2,3)\) を反転し \((3,2,1)\) とし、並び替えることによって \((4,5,6,3,2,1)\) などを得ます。

数列を分けるとき、\(i,i+1\) の間を仕切り \(i\) ということにします。 仕切り \(1,2,\dots,N-1\) からいくつか選ぶことを考えます。連続している \(2\) 個の仕切りを選ぶと \(\frac{1}{2}\) をかけることとなります。 なので、連続している \(N\) 個の仕切りから \(K\) 個選んでいて、仕切り \(1,N\) をそれぞれ選んでいるかどうかを持つことでダブリングで計算量 \(O(N \log N)\) で各 \(i\) に対して \(i\) 個の部分列に分け、反転する方法の個数を求めることができます。

\(M\) が一般の場合を考えます。 ここで、\(Q_{P_i} =i \) となる順列 \(Q\) を取ります。すると \(|P_i - P_{i+1}|=M \Leftrightarrow |Q_i-Q_{i+M}|=1\) が成り立つため、\(Q\) の index を \(\bmod K\) で分けて考えると \(M=1\) の場合に帰着することができます。これらの結果を \(\mathrm{O}(N\log^2 N)\) でマージしておきます。

\(K\) を固定した場合の答えを \(A_K\) と置きます。今求められているものは \(0 \le i \le N-1\) に対する \(\sum_{j=0}^{N-1} \binom{j}{i} A_j\) です。これを \(B_i\) と置きます。

\(B_i = \sum_{j=0}^{N-1} \binom{j}{i} A_j\) を適切に置き換えることにより \(B_i = \sum_{j=0}^{N-1} \frac{A_j}{(j-i)!}\) となります。 上記の式より \(A_j\) を上から分割統治 FFT で確定させることができます。

よってこの問題を \(\mathrm{O}(N\log^2 N)\) で解くことができました。