RainAir
My OI Blog
RainAir
「CF1097G」Vladislav and a Great Legend

CF1097G

题意大概是给 $n$ 个点的树,定义 $f(S)$ 表示 $S$ 中所有的点构成的斯坦纳树的大小。求
$$\sum_{S \subseteq [1,2,\cdots,n],S \neq \emptyset} f(S)^k$$
解:首先看到 $k$ 次方和发现不太好求,我们可以拆成斯特林数的形式:
$$x^k = \sum_{i=0}^k i! (^x_i) \{^k_i\}$$
其中 $\{^a_b\}$ 表示第二类斯特林数,组合意义是将 $a$ 个有标号的求放进 $b$ 个无标号的箱子的方案数。
考虑组合意义,枚举最后一个球怎么放可以写出递推方程:
$$\{^n_m\} = m\{^{n-1}_ m\} + \{^{n-1}_ {m-1}\}$$
边界状态为 $\{^0_0\} = 1$
然后我们考虑为什么对 $x^k$ 的展开是对的:我们只需要考虑组合意义是否相同。
左边的组合意义:有 $k$ 个球,$x$ 中颜色,染色方案是 $x^k$
右边的组合意义:首先将相同颜色的球锁起来,枚举有多少种不同颜色的球 $i$,首先要从这 $x$ 种颜色选出 $i$ 中互不相同的颜色 ($(^x_i)$),然后要将这个 $k$ 个球染上 $i$ 种颜色(相当于将 $k$ 个 有标号的球放入 $i$ 个有标号的箱子里,也就是 $i! \{^k_i\}$)
所以左右两边组合意义相同,等式成立。
然后代入原式可以得到
$$\sum_{S} \sum_{i=0}^k i! (^{f(S)}_ i) \{^k_i\}$$
$$\sum_{i=0}^k i! \{^k_i\} \sum_{S} (^{f(S)}_ i)$$
发现我们只需要算 $\sum_{S} (^{f(S)}_ i)$ 了,这个式子其实计算的是所有点集的斯坦纳树中选择 $i$ 条边的方案数,这个树形背包做就好了。
设 $f_{i,j}$ 表示以 $i$ 为根的子树内选择了 $j$ 条边的方案数,转移时考虑:
1. 不选这个子树
2. 只选这个子树
3. 同时选这个子树和其他子树

就可以了。最后代入原式计算即可。

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/747
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

「CF1097G」Vladislav and a Great Legend
CF1097G 题意大概是给 $n$ 个点的树,定义 $f(S)$ 表示 $S$ 中所有的点构成的斯坦纳树的大小。求 $$\sum_{S \subseteq [1,2,\cdots,n],S \neq \emptyset} f(S)^k$$ 解:首先看到 $k$ 次…
扫描二维码继续阅读
2019-08-03
标签
近期评论