2020 年 “游族杯” 全国高校程序设计网络挑战赛热身赛

Cuber QQ has a sequence $b$ of bits. The length of the sequence is $n$ . Cuber CC also has a favorite integer $m$ which is between $1$ and $n$ , inclusive.

A sequence of $n$ bits is called a rotator sequence if it has the following property: its prefix of length $n-m$ is equal to its suffix of length $n-m$ .

For example, let $m = 2$ . Consider the sequence $b = 10101010$ . Its length is $n = 8$ , so we have $n - m = 6$ .

The prefix of length $6$ is $101010$ , the suffix of length $6$ is $101010$. They are the same, so this $b$ is a rotator sequence. Now consider $b = 11010100$ . For this $b$ we compare the prefix $110101$ to the suffix $010100$. They differ, so this $b$ is not a rotator sequence.

Cuber QQ wants to change her sequence $b$ into some rotator sequence. She will produce such a sequence
in a sequence of steps. In each step she can do one of the following two types of changes to the sequence:

• Flip any bit (from $1$ to $0$ or from $0$ to $1$ ).
• Flip the first $k \cdot m$ bits, for any positive integer $k$ .

You are given $b$ : each of its characters will be either ‘ $0$ ‘ or ‘ $1$ ‘. Find the minimal number of steps required to obtain some rotator sequence.