自动搬运

查看原文

来自洛谷，原作者为

	Sampson_YW 你弱归你弱，YW比你弱。

搬运于2025-08-24 22:52:46，当前版本为作者最后更新于2023-12-12 10:57:25，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

设一个集合 $A$ 表示所有为 2 的下标集合。我们要求的就是：所有操作中恰好包含了 $A$ 的方案数。

恰好不好算，可以容斥成至多。枚举一个集合 $S$，表示这个集合里的位置可以被包含，这个集合之外的位置不能被包含，容斥系数为 $(-1)^{|A|-|S|}$。容易发现这两种状态是和题目中 0,1 的状态是一样的。那么就将 $S$ 中的数看成 0，$S$ 之外的数看成 1。容斥系数的指数就是有多少个 2 被看成了 1。

于是现在变成了对一个 01 序列求答案。这是容易计算的，所有不包含任意一个 1 的区间都可以选，方案数就是这些区间数量的 $m$ 次方。考虑区间数量如何计算：设 $X$ 为 1 的下标序列（为了方便计算，设第 $0$ 位和 $n+1$ 位上的数是 1），那么区间数量就是 $\sum \binom{X_i-X_{i-1}}{2}$。

因此区间数量只与这个下标序列有关，考虑 DP。设 $f_{i,k}$ 表示 $i$ 在下标序列中，$i$ 之前的区间数量为 $k$。转移枚举下一个在下标序列中的数 $j$，要满足 $[i+1,j-1]$ 中没有 1。令 $w=\binom{j-i}{2}$。

如果 $j$ 是 1，那么 $f_{i,k}$ 转移到 $f_{j,k+w}$。

如果 $j$ 是 2，那么转移时要乘上一个容斥系数 $-1$，即 $-f_{i,k}$ 转移到 $f_{j,k+w}$。

答案为 $\sum k^mf_{n+1,k}$。code