We can rephrase the operation as follows.(same as the official editorial)

• 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).

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

Then we can rephrase this problem as a XOR convolution problem:

• Given two arrays \(a,b\), let two arrays \(A,B\) satisfying \(A_i = a_{\text{popcount}(i)},B_i = b_{\text{popcount}(i)}\), find the XOR convolution of array \(A\) and \(B\). (In other words, \(A,B\)’s all popcount-equal positions have the same value.)

We can prove that, let \(C\) be the XOR convolution of array \(A\) and \(B\), there exists an array \(c_i\) satisfies \(C_i=c_{\text{popcount}(i)}\).

If we can solve the above problem, we can solve this problem by letting \(a_i=A(i)/10^9,b_i = [i=1]\), and calculate the XOR convolution of \(a\) and \(K\) times of \(b\).

To solve the above problem, we need to calculate the \(\text{FWT}\) value of the special array \(F\) satisfying \(F_i = f_{\text{popcount}(i)}\).

Let \(G=\text{FWT}(F)\) , \(f_k = \sum_{\text{popcount}(s)=k}F_s\) , \(g_i = \sum_{\text{popcount}(s)=i}G_s\).

The formula of \(\text{FWT-XOR}\) is:

\[G_{s} = \sum_{t} F_{t}(-1)^{\text{popcount}(s)(t\&s)}\]

By enumerating how many bits of \(s\) and \(t\) are the same, we can find that:

\[g_k = \sum_{i=0}^{n} f_i (1-x)^i(1+x)^{n-i}[x^k]\]

By using divide-and-conquer and polynomial multiplycation, we can calculate the above formula in \(O(n\log^2 n)\) time.

Sample Code

We can also optimize this to \(O(n\log n)\) as follows.

\[\sum_{i=0}^{n} f_i (1-x)^i(1+x)^{n-i}\]

\[\sum_{i=0}^{n} f_i (x-1)^i((x-1)+2)^{n-i}\]

\[\sum_{i=0}^{n} \sum_{j=0}^{n-i} f_i (x-1)^{i+j}2^{n-i-j}\binom{n-i}{j}\]

let \(k=i+j\), we should find:

\[h_k = \sum_{i=0}^n f_i \binom{n-i}{k-i}\]

The answer polynomial equals to:

\[\sum_{k=0}^n h_k2^{n-k}(x-1)^k\]

We can use convolution to calculate it by \(O(n\log n)\).