## Editorial for Canada Day Contest 2021 - 0-1

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Aaeria

#### Chapter 1

There are ways of choosing of the bits. Each set of bits has a chance of being flipped.

For Subtask 1, use dynamic programming. Let be the probability of having the string after moves. Use the transition for every generated by flipping bits on . Complexity: For Subtask 2, generate a matrix where is the chance of becoming in one second. Find the answer by calculating . Complexity: #### Chapter 2

Solution by arvindr9 depends only on the value of xor . Let be the probability going from any to ( xor ) after seconds. Now you've reduced from a 2D matrix into a 1D array of length .

You can do an xor convolution of and to get . Now you can find and solve the problem with complexity , solving Subtask 3.

To solve Subtask 4, use the Fast Walsh–Hadamard transform to speed up the xor convolutions and find the answer in .

#### Chapter 3 is the same for all that share a value of . So you can actually compress further into an array of length . This optimization leads to an 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 - enough to complete the problem.

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