首先考虑一些简单的情况，比如 \(m=1\)。
容易发现操作 1 和操作 2 的顺序不会影响结果，于是可以钦定所有操作 1 在操作 2 之前。并且可以发现，进行完所有 1 后 2 的次数即为 \((\text{连续段个数}-1)\)。
然后考虑将 \(m>1\) 的情况。显然最后序列上每 \(m\) 长度分一段，则每一段都相同，最后一段例外，是和其他段的一段等长前缀相同。那么设最后每段都为 \(S\)，一开始每段的状态为 \(A_i\)，则在所有操作 2 之前，都有 \(S=A_i\) 或 \(S=flip(A_i)\)。\(flip(X)\) 表示把 \(X\) 串内所有数 \(\oplus 1\)。然后定义一个序列 \(c_i\) 表示第 \(i\) 段有没有被 \(flip\)。则与 \(m=1\) 时一样，需要进行操作 2 的次数即为 \(c\) 的连续段个数。
上面的是 naive 的，相信大家赛时都想出来了。
然后考虑如何解决这个转化后的问题。如果考虑 dp，则会发现不管将这个状态和操作 1 还是 2 联系起来，都会对另一种操作有后效性。很难设计状态。贪心什么的就更难了。
此时发现我们的路已经被堵死了。那就要从头开始考虑这个问题。
我们观察一下数据范围，\(n\leq300\)。很像一个 \(n^3\) 的问题。但是刚才已经基本否定了常规解法。
你突然想到 \(m\) 长度一段，就共有 \(\left\lceil\dfrac{n}{m}\right\rceil\) 段。看到这个分数，联系 \(n\leq300\)，你发现 \(\sqrt n\leq20<\log 10^6\)。你发现你可以根号分治！
- \(m\leq\sqrt n\)
则上文的 \(S\) 长度 \(\leq 20\)。暴力状压 \(S\)，对于每一种 \(S\)，考虑 dp。设 \(dp_{i,0/1}\) 为当前处理到第 \(i\) 段，有没有翻转的最小操作数。则有：
\[dp_{i,j}=\min(dp_{i-1,j}+\operatorname{popcount}(S\oplus c_i\oplus(j\times (2^m-1)),dp_{i-1,j\oplus 1}+\operatorname{popcount}(S\oplus c_i\oplus(j\times (2^m-1)))+1) \]其中 \((j\times (2^m-1))\) 部分是要看这一段是否翻转，\(+1\) 则是因为新增连续段。
初始状态为 \(dp_{0,0}=0\)
最后一个不完整的段要特殊处理，差别不大。
- \(m>\sqrt n\)
则段数 \(\leq 20\)。暴力状压 \(c\)，然后处理 \(S\)。根据 \(S\) 当前位 \(0/1\) 的数量，贪心地选择更小的，再加上操作 2 次数。全部取最小值即为答案。
时间复杂度 \(O(2^{\sqrt n}\times n)\)。挺稳的。
以上内容纯属杜撰。
标签：9134,题解,sqrt,times,一段,操作,oplus,dp,翻转 From： https://www.cnblogs.com/yinhee/p/fanzhuanyingbi.html