Tatar TV Show

Observation 1: positions only talk to the same residue

A move chooses $i$ and $i+k$. These positions have the same remainder modulo $k$, so the string splits into independent chains:

$$r, r+k, r+2k, \ldots$$

for $r=1,2,\ldots,k$, ignoring terms greater than $n$. No move ever mixes two chains. TV magic? Nope, just modular arithmetic.

Observation 2: parity is immortal

Inside one chain, every move flips exactly two bits of that chain. Therefore the parity of the number of ones in the chain is invariant:

$$P_r = \sum_{j \ge 0, r+jk \le n} [s_{r+jk}=1] \pmod 2.$$

The all-zero string has $P_r=0$ for every $r$. So if any residue class has an odd number of ones, the answer is immediately NO.

Why even parity is also enough

This is where people sometimes summon linear algebra. You can, but a greedy proof is cleaner and has fewer demons.

Take one chain:

$$a_0, a_1, \ldots, a_m.$$

Scan it left to right. For $j=0$ to $m-1$:

• if the current bit at $a_j$ is $0$, do nothing;
• if it is $1$, apply the move that toggles $a_j$ and $a_{j+1}$.

After this, $a_j$ becomes $0$ and will never be touched again. At the end, only $a_m$ could be nonzero. But the parity of the chain never changed, and all previous bits are now zero, so the last bit equals the chain parity. If that parity was even, it is also $0$.

So each chain can be killed independently iff its number of ones is even.

Algorithm

For each test case:

1. Create parity of size $k$, initialized to $0$.
2. For every 0-based index $i$, if $s_i=1$, flip parity[i % k].
3. If all entries are $0$, print YES; otherwise print NO.

In 0-based indexing, positions connected by a move still differ by exactly $k$, so they have the same value of $i \bmod k$.

Complexity

For one test case, we scan the string and the $k$ buckets:

$$O(n+k)=O(n)$$

because $k \le n$. Over all tests:

$$O\left(\sum n\right)$$

time, with $O(k)$ memory. Tiny. No drama.