P9891

Sampson_YW · 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