12.9 模拟赛

摆烂太久了。趁着还没搞文化课，维护一下博客、

A

是我太弱了。

部分分 $k=1$。

拆贡献，变成求每种颜色在几种方案里出现过。

发现颜色是对称的，所以只用求 $G(1)$。

把存在变成不存在，求 $总方案-G(1)$。

设 $f_{u,0/1}$ 表示 $u$ 的子树，$u$ 的颜色是否为 $1$ 的方案数。

简单转移，注意对于 $u \in S$ 钦定 $f_{u,1}=0$。

正解

不能拆贡献了。要求 $\sum_cg(c,S)^k$。

由第二类斯特林数，$x^k=\sum_{i=0}^x \binom{x}{i}i!S(k,i)$。

带入得：$ans=\sum_c\sum_{i=0}^k \binom{g(c,S)}{i}i!S(k,i)=\sum_{i=0}^ki!S(k,i)\sum_c\binom{g(c.S)}{i}$​。$^{[1]}$​

只要求出 $G(i)=\sum_c\binom{g(c,S)}{i}$ 就行了。

仿照 $k=1$，我们令 $h(i)$ 表示某个大小为 $i$ 的颜色集合几种方案中完整地出现过。

则 $G(i)=\binom{m}{i}h(i)$。

把存在变成不完全存在，设 $dp(i)$ 表示钦定某个集合必须不出现。

那么 $h(i)=总方案-\sum_{j=0}^i (-1)^j\binom{i}{j}dp(j)$。

由于 $i$ 是 $O(k)$ 级别的，所以直接跑 $k$ 遍树形 dp 算即可。

$^{[1]}$：这里巧妙地把枚举的上界改为 $k$。由于 $i>k$ 时 $S(k,i)$ 为 $0$，所以不影响值。但是 $i$ 的范围从 $O(n) \rarr O(k)$。