Chapter 1

There are ~\binom n x = \frac{n!}{x!(n-x)!}~ ways of choosing ~x~ of the ~n~ bits. Each set of ~x~ bits has a ~\frac{x!(n-x)!}{n!}~ chance of being flipped.

For Subtask 1, use dynamic programming. Let ~dp[i][s]~ be the probability of having the string ~s~ after ~i~ moves. Use the transition ~dp[i][s]=\sum \frac{x!(n-x)!}{n!} dp[i-1][s']~ for every ~s'~ generated by flipping ~x~ bits on ~s~. Complexity: ~\mathcal O((2^n)^2 K)~

For Subtask 2, generate a matrix ~p~ where ~p[s][t]~ is the chance of ~s~ becoming ~t~ in one second. Find the answer by calculating ~p^K~. Complexity: ~\mathcal O((2^n)^3 \log K)~

Chapter 2

Solution by arvindr9

~p[s][t]~ depends only on the value of ~s~ xor ~t~. Let ~p_i[x]~ be the probability going from any ~s~ to (~s~ xor ~x~) after ~i~ seconds. Now you've reduced ~p~ from a 2D matrix into a 1D array of length ~2^n~.

You can do an xor convolution of ~p_a~ and ~p_b~ to get ~p_{a+b}~. Now you can find ~p_K~ and solve the problem with complexity ~\mathcal O((2^n)^2 \log K)~, solving Subtask 3.

To solve Subtask 4, use the Fast Walsh–Hadamard transform to speed up the xor convolutions and find the answer in ~\mathcal O(2^n n \log K)~.

Chapter 3

~p[s]~ is the same for all ~s~ that share a value of ~\operatorname{popcount}(s)~. So you can actually compress ~p~ further into an array of length ~n~. This optimization leads to an ~\mathcal O(n^2 K)~ DP solution which alone is enough to solve subtasks 1-3.

Next, you'll need to return to the matrix technique from subtask 2. But this time, you have an algorithm with a complexity of ~\mathcal O(n^3 \log K)~ - enough to complete the problem.

Bonus: Even now you can take advantage of symmetries in the matrix for constant time improvements.