Contest Duration: - (local time) (100 minutes) Back to Home

## F - Minflip Summation Editorial by en_translator

The answer for the subproblem is, if the first letter of $$T'$$ is 0, the number of times that 0 becomes 1 when inspecting $$T'$$ in order from the first, or if the first letter of $$T'$$ is 1, the number of times that 1 becomes 0 when inspecting $$T'$$ in order from the first.
So, the problem can be solved this problem by a fast matrix exponentiation with the following five states:

• The first letter is 0 and the last letter is 0
• The first letter is 0 and the last letter is 1
• The first letter is 1 and the last letter is 1
• The first letter is 1 and the last letter is 0
• The answer for the subproblem for the characters currently inspected

Since ? can be seen as a superposition of 0 and 1, the matrix corresponding to ? is equal to the sum of the matrix corresponding to 0 and the matrix corresponding to 1.
By calculating the matrix for the second through the last character of $$T$$, and applying it to the first character of $$T$$, one can obtain the answer.
The total time complexity is $$O(|S| + \log K)$$.

Sample Code (C++)

posted:
last update: