まず操作は次のように言い換えられます．

• 長さ \(N\) の \(01\) 列があり，そのうち \(x\) 個が \(1\) である． 文字を一つランダムに選び，flip (\(0\) と \(1\) を入れ替える) する．

最初に \(a\) 個 \(1\) があり，\(K\) 回の操作後に \(b\) 個 \(1\) がある場合の数を考えましょう．

ここで，\(2\) 変数 \(x,y\) の多項式として， \(f_{even}=y (\sum_{i \equiv 0 \mod 2} x^i/i!) + (\sum_{i \equiv 1 \mod 2} x^i/i!)\)，\(f_{odd}=(\sum_{i \equiv 0 \mod 2} x^i/i!) + y(\sum_{i \equiv 1 \mod 2} x^i/i!)\) を定義します． ここで，\(x\) の次数は操作回数，\(y\) の次数は最終的に \(1\) になる個数に対応しています． このとき求めるべき値は，\(f_{even}^af_{odd}^{N-a}\) の \(x^Ky^b\) の係数になります．（正確には最後に \(K!/N^K\) をかける必要がありますが，一旦無視します．）

\(P=(y+1)exp(x),Q=(y-1)exp(-x)\) と定義すると，\(\sum_{0 \leq a \leq N} A_a(P+Q)^a(P-Q)^{N-a}\) が計算できれば良いことになります．（ここでも定数倍を無視しています．）

\(\sum_{0 \leq a \leq N} A_a(P+Q)^a(P-Q)^{N-a}\) を計算した結果は，何らかの \(w_0,w_1,\cdots,w_N\) を用いて，\(\sum_{0 \leq i \leq N} w_iP^iQ^{N-i}\) と書けます． ここで，\(P^iQ^{N-i}\) の \(x\) 成分について考えると，これは \(exp((2i-N)x)\) になっているので，\(x^K\) の係数は \((2i-N)^K/K!\) と求まります．（最初に無視した \(K!\) の項と合わせると，\((2i-N)^K\) となり，簡単に計算できます．）

結局，\(\sum_{0 \leq i \leq N} w_i (2i-N)^K (y+1)^i(y-1)^{N-i}\) を計算すればよいことになります．

\(\sum_{0 \leq a \leq N} A_a(P+Q)^a(P-Q)^{N-a}\) および \(\sum_{0 \leq i \leq N} w_i (2i-N)^K (y+1)^i(y-1)^{N-i}\) を計算するためには，次のような問題が解ければよいです．

• 整数列 \(C_0,C_1,\cdots,C_N\) が入力で与えられるので，\(\sum_{0 \leq i \leq N} C_i (z+1)^i (z-1)^{N-i}\) を \(z\) の多項式として求めよ．

これは分割統治によって求めることができます． 具体的には，\(C\) の前半分と後ろ半分でそれぞれ問題を再帰的に解き，それぞれに \((z-1)\) の冪および \((z+1)\) の冪をかけて足せばよいです．

多項式の掛け算に FFT を用いることで，計算量は全体で \(O(N\log^2 N)\) になります．

解答例(c++)

おまけ：\(\sum_{0 \leq i \leq N}C_iz^i(z-2)^{N-i}\) を経由することで，\(O(N \log N)\) で解くことも可能です．（この解法は EntropyIncreaser さんの提出を参考にしています）実装例(c++)