「EOJ 181B」Bits（数据分治）

题目大意

给定一个长度为 $n$ 的 01 串和一个正整数 $m$。你要进行一系列操作，将串变为有长度为 $m$ 的循环节的串。操作一共有两种：

• 将串的某一位反转。
• 将串的一个长度为 $k \times m$ 的前缀全部反转。其中 $1 \le k \le \frac{n}{m}$。

问至少进行几次操作。

数据范围：$n \le 300, m \le n$。

思路分析

我们令 $M = \lfloor \frac{n}{m} \rfloor$。

先考虑 $m$ 较大的情况。

发现第二种操作最多只有 $M$ 种，我们暴力枚举每个操作是否使用，然后对于操作后的串计算使用第一种操作最少的次数即可。复杂度看似是 $2^M \times n$ 的，但实际上可以通过 DFS 来优化到 $O(2^M \times m)$。

再考虑 $m$ 较小的情况。

发现最终得到的串最多只有 $2^m$ 种，我们枚举每个串，然后处理出那些位置需要被反转，再用 DP 来计算最少修改次数即可。当然，也可以对于 $2^m$ 个串整体进行一次 DP。注意为了无后效性，DP 要倒序做。时间复杂度 $O(2^m \times M)$。

所以，我们当 $m \ge \sqrt{n}$ 的时候用第一种方案，否则用第二种方案即可。总时间复杂度：

$$O(2^{\sqrt{n}} \times \sqrt{n})$$

（为啥这个题 $n$ 不出到 $400$ 啊 QAQ）

代码实现

#include <cstdio>