题解：P10461 多项式复合集合幂级数
喵仔牛奶
·
·
题解
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)。