0-1 Solution

You have a quantum computer containing two binary strings ss and tt, both of length nn. Every second, xx of the nn bits on ss are randomly chosen and flipped. Find the probability that after KK seconds, ss will become tt.

See Also : Canada Day Contest 2021

Constraints

x≤nx≤n

Subtask	Score	Constraints
1	10%	n≤6,K≤100n≤6,K≤100
2	12%	n≤7,K≤700000n≤7,K≤700000
3	18%	n≤10,K≤900000n≤10,K≤900000
4	12%	n≤16,K≤109n≤16,K≤109
5	48%	n≤128,K≤109n≤128,K≤109

Input Specification

The first line contains three integers, nn, xx, and KK.

The next line contains the string ss.

The last line contains the string tt.

Output Specification

Find the probability of turning ss into tt. If the probability is ABAB, print AB−1(mod109+7)AB−1(mod109+7). It can be proven that the result is rational.

Sample Input 1

4 1 2
0000
0000

Sample Output 1

250000002

Explanation For Sample 1

The probability is 1414.

Sample Input 2

4 2 1
0000
0000

Sample Output 2

Sample Input 3

6 4 3
010000
100000

Sample Output 3

932444451

Sample Input 4

6 1 43
010000
011110

Sample Output 4

242545047

Sample Input 5

6 3 0
010000
010000

Sample Output 5

Sample Input 6

1 1 9
0
1

Sample Output 6

Chapter 1

There are (nx)=n!x!(n−x)!(nx)=n!x!(n−x)! ways of choosing xx of the nn bits. Each set of xx bits has a x!(n−x)!n!x!(n−x)!n! chance of being flipped.

For Subtask 1, use dynamic programming: let dp[i][s]dp[i][s] be the probability of having the string ss after ii moves. Use the transition dp[i][s]=∑x!(n−x)!n!dp[i−1][s′]dp[i][s]=∑x!(n−x)!n!dp[i−1][s′] for every s′s′ generated by flipping xx bits on ss. Complexity: O((2n)2K)O((2n)2K)

For Subtask 2, generate a matrix pp where p[s][t]p[s][t] is the chance of ss becoming tt in one second. Find the answer by calculating pKpK. Complexity: O((2n)3logK)O((2n)3log⁡K)

Chapter 2

p[s][t]p[s][t] depends only on the value of ss xor tt. Let Let pi[x]pi[x] be the probability going from any ss to (ss xor xx) after ii seconds. Now you’ve reduced pp from a 2d matrix into an 1d array of length 2n2n.

You can do an xor convolution of papa and pbpb to get pa+bpa+b. Now you can find pKpK and solve the problem with complexity O((2n)2logK)O((2n)2log⁡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 O(2nnlogK)O(2nnlog⁡K).

Chapter 3

p[s]p[s] is the same for all ss that share a value of popcount(s)popcount(s). So you can actually compress pp further into an array of length nn. This optimization leads to an O(n2K)O(n2K) 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 O(n3logK)O(n3log⁡K) – enough to complete the problem.

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

0-1 Solution | Canada Day Contest 2021