First, we rephrase the operation as follows.

• We have a \(01\)-sequence of length \(N\), where \(x\) characters are \(1\). Choose a random character and flip it (\(0\) becomes \(1\) and vice versa).

Let us count the number of ways that begin with \(a\) \(1\)’s and end with \(b\) \(1\)’s after \(K\) operations.

Here, let us define polynomials of two variables \(x,y\): \(f_{even}=y (\sum_{i \equiv 0 \mod 2} x^i/i!) + (\sum_{i \equiv 1 \mod 2} x^i/i!)\) and \(f_{odd}=(\sum_{i \equiv 0 \mod 2} x^i/i!) + y(\sum_{i \equiv 1 \mod 2} x^i/i!)\). Here, the degree of \(x\) corresponds to the number of operations, and the degree of \(y\) corresponds to the final number of \(1\)’s. The value we seek is the coefficient of \(x^Ky^b\) in \(f_{even}^af_{odd}^{N-a}\) (multiplied by \(K!/N^K\), to be precise, but we ignore it now).

If we define \(P=(y+1)exp(x),Q=(y-1)exp(-x)\), what we want to compute is \(\sum_{0 \leq a \leq N} A_a(P+Q)^a(P-Q)^{N-a}\) (multiplied by some constant, but again we ignore it here).

The result of computing \(\sum_{0 \leq a \leq N} A_a(P+Q)^a(P-Q)^{N-a}\) can be written as \(\sum_{0 \leq i \leq N} w_iP^iQ^{N-i}\) using some \(w_0,w_1,\cdots,w_N\). Here, the \(x\)-component of \(P^iQ^{N-i}\) turns out to be \(exp((2i-N)x)\), so the coefficient of \(x^K\) can be found as \((2i-N)^K/K!\). (Combining it with the term \(K!\) which we first ignored, we have \((2i-N)^K\), which can be easily computed.)

Eventually, what we want to compute is \(\sum_{0 \leq i \leq N} w_i (2i-N)^K (y+1)^i(y-1)^{N-i}\).

To compute \(\sum_{0 \leq a \leq N} A_a(P+Q)^a(P-Q)^{N-a}\) and \(\sum_{0 \leq i \leq N} w_i (2i-N)^K (y+1)^i(y-1)^{N-i}\), the following problem should be solved.

• Given an integer sequence \(C_0,C_1,\cdots,C_N\) as the input, find \(\sum_{0 \leq i \leq N} C_i (z+1)^i (z-1)^{N-i}\) as a polynomial of \(z\).

This can be solved by divide and conquer. Specifically, we should solve the problem on the former and latter halves of \(C\) recursively, multiply them by powers of \((z-1)\) and \((z+1)\), respectively, and then add them.

By using FFT in multiplications of polynomials, the total complexity will be \(O(N\log^2 N)\).

Sample Solution (c++)

Note: It is possible to solve the problem in \(O(N \log N)\) time by calculating \(\sum_{0 \leq i \leq N} C_i z^i (z-2)^{N-i}\). Shout-out to EntropyIncreaser! Sample Solution(c++)