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

**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:

#### 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

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.

## Comments