自动搬运

查看原文

来自洛谷，原作者为

	喵仔牛奶 黄昏再美终要黑夜。

搬运于2025-08-24 22:58:10，当前版本为作者最后更新于2025-05-19 14:57:17，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Solution

设 $f_{k,S}$ 表示 $[x^S]F^k(x)$，$g_{i}$ 表示 $[x^n]G(x)$。集合幂级数的乘法是子集卷积。

考虑 $\sum_{k=0}^{n}g_k\times f_{k,S}$ 的组合意义：初始集合为 $S$，每次删一个包含 $\max S$ 的子集，如果删了 $k$ 次有 $g_k\times k!$ 的贡献。注意这里的正确性依赖 $f_{1,\varnothing}=0$。

设 $[x^S]H_{i,j}(x)$ 表示删除了 $j$ 次后集合变为 $S$，且 $\max S\le i$，这种情况下所有删 $S$ 方案的贡献和。

初始时 $h_{0,i,\varnothing}=g_i\times i!$。考虑从小到大枚举 $i$，刷表法转移：

• 存在一次删除，满足 $i=\max S$ 的情况：设 $F_i(x)=\sum_S f_S[i=\max S]$，$H_{i,j-1}\gets H_{i,j-1}+H_{i-1,j}\times F_i$。
• 不存在这样的删除的情况：原样转移，$H_{i,j}\gets H_{i,j}+H_{i-1,j}$。

显然，$H_{n,0}$ 即为答案。

转移时忽略 $\max S>i$ 的集合，时间复杂度为 $\sum_{i=0}^{n}(n-i)i^22^i=\mathcal O(n^22^n)$。使用滚动数组压掉第一维，空间复杂度为 $\mathcal O(n2^n)$。