PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Daanish Mahajan
Preparer: Utkarsh Gupta
Testers: Jeevan Jyot Singh, Hriday
Editorialist: Nishank Suresh
DIFFICULTY:
2432
PREREQUISITES:
None
PROBLEM:
Given a binary string of length N and an integer K, in one move you can flip any subsequence of the string of length K. How many distinct strings can you obtain using zero or more moves?
EXPLANATION:
The actual binary string S doesn’t matter at all — only the values of N and K matter, since each string you can obtain is uniquely determined by the set of positions flipped.
So the question boils down to the following: given N and K, how many subsets of positions can we flip?
The answer has three cases:
- If N = K, obviously either we flip nothing or we flip everything, so the answer is 2
- Otherwise, K \lt N, and:
- If K is odd, we can flip any subset of positions, so the answer is 2^N
- If K is even, we can flip any subset of positions of even size, so the answer is the number of subsets of even size, i.e, 2^{N-1}
Proof
The N = K case is trivial, so let’s look at K \lt N.
First, let K be odd. It’s enough to show that any single position can be flipped without changing the state of any of the other positions, since this allows us to flip any subset by repeatedly applying it. So, let’s show that position 1 can be flipped.
Construction
Consider the positions 1, 2, \ldots, K+1.
There are \binom{K}{K-1} = K ways to choose a subset of size K-1 from positions 2, \ldots, K+1. To each of these K subsets, insert 1 to obtain a size-K subset.
Now perform K flipping moves, one on each of the subsets we have. Note that:
- Position 1 is flipped K times (an odd number), and so is flipped at the end
- Positions 2, 3, \ldots, K+1 are flipped K-1 times (an even number) each, and so aren’t flipped at the end
- Positions \gt K+1 are untouched.
So, only position 1 is flipped, as required.
Next, let K be even. Note that in this case, after each operation the number of positions flipped will be even. It thus remains to show that any even-sized subset is attainable.
Construction
Similar to the odd case, we will show that positions 1 and 2 can be flipped without affecting the rest of the string. Chaining together operations of this type allows any even-sized subset to be formed.
The construction is also essentially the same: there are K-1 ways to choose a subset of size K-2 from \{3, 4, \ldots, K+1\}. To each of these, insert 1 and 2 to obtain a size K subset, and operate on each one.
- Positions 1 and 2 flip K-1 times, which is odd.
- Positions 3 to K+1 flip K-2 times each, which is even
So, at the end only 1 and 2 are flipped and we are done.
Make sure to compute the above values modulo 10^9 + 7.
TIME COMPLEXITY
\mathcal{O}(N) per test case.
CODE:
Editorialist's code (Python)
mod = int(10**9 + 7)
for _ in range(int(input())):
n, k = map(int, input().split())
s = input()
if k == n:
print(2)
elif k%2 == 1:
print(pow(2, n, mod))
else:
print(pow(2, n-1, mod))