自动搬运

查看原文

来自洛谷，原作者为

	lmh .

搬运于2025-08-24 23:15:12，当前版本为作者最后更新于2025-05-02 16:27:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

一个比官方题解更简单的做法。

数据范围与 T1 不同，这里 $n\le 5000$，所以 $O(n^2)$ 的时间复杂度是可以接受的。这启发我们设计一个二维的 dp 解决问题。

$m=2$ 的情况是简单的：将偶数位取反（$1$ 变成 $2$，$2$ 变成 $1$）之后相当于需要进行若干次操作使每一位都相同，此时唯一的最优策略是修改所有出现次数更少的数字，所以 $\sum [f(a,n,m)=i]g(a,n,m)=2\binom{n}{i}$。

否则，我们考虑任意一个最优策略，它在每个长度为 $l$ 的全部相等的连续段当中一定修改了 $[\frac{l}{2}]$ 个位置。

令 $0$ 表示没有进行修改，$1$ 表示进行了修改操作，则 $l$ 为奇数时，唯一的可能是形如 $0101010\cdots0$。

而 $l$ 为偶数时，一定存在一个偶数位置作为分界点，前面形如 $0101010\cdots1$，后面形如 $101010\cdots0$。

将它们分割成若干个 $01$ 和 $10$，如果 $l$ 为奇数就把最后一个 $0$ 单独拿出来。

现在对这个分割状态进行 dp，令 $f_{i,j,0/1/2}$ 为前 $i$ 个数进行了 $j$ 次修改，最后一个连续段形如 $0/01/10$ 的方案数。

这里定义一种“方案”为：在这 $i$ 个位置内填入 $[1,m]$ 的数作为原来的 $a$，再在放了 $1$ 的位置上进行修改使得相邻位互不相同。

初始令 $f_{1,0,0}=m,f_{2,0,0}=f_{2,0,1}=f_{2,0,2}=m(m-1)$。

转移方程为：

$$f_{i,j,0}=(f_{i-1,j,0}+f_{i-1,j,1}+f_{i-1,j,2})(m-1) $$$$f_{i,j,1}=(f_{i-2,j-1,0}+f_{i-2,j-1,1}+f_{i-2,j-1,2})(m-1)^2 $$

每一位不能和前面一位相同，没有额外限制。

$$f_{i,j,2}=(m-1)(m-2)f_{i-2,j-1,0}+(f_{i-2,j-1,1}+f_{i-2,j-1,2})(m-1)^2 $$

注意这里从 $f_{i-2,j-1,0}$ 转移时第 $i$ 位不能和第 $i-2$ 位相同，因为这样会造出一个长度为奇数的连续段，它在 $f_{i,j,0}$ 中被统计。

之后就可以做到 $O(n^2)$ 了。可以用倍增 + FFT 做到 $O(n\log n)$ 但是我没写。