Chapter 1

There are $(\genfrac{}{}{0ex}{}{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^{\prime }]$ for every $s^{\prime }$ 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 $\mathrm{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.