loj 3102

题目大意:

给定 $m$ 棵无向树$\left\{T_{1}=\left(V_{1}, E_{1}\right), T_{2}=\left(V_{2}, E_{2}\right), \cdots, T_{m}=\left(V_{m}, E_{m}\right)\right\}$构成的森林。定义无向边集$E^\ast = \left\{ \left( u, v \right) \mid u \in V_i, v \in V_j, i \neq j \right\}$.令 $G=(V,E)$，其中 $ V = V_1 \cup V_2 \cup \cdots \cup V_m, E = E_1 \cup E_2 \cup \cdots \cup E_m \cup E^\ast$ .

你需要求出 $G $ 的 Hamilton 回路的数量。

对于每一颗树，先求出 $ways_i$ 表示在这颗树上选出 $i$ 条链的方案数。

现在的问题就是要把若干条链拼成一个环，同色不相邻。

先破环成链。对于一颗树，他的指数生成函数是 $\sum_{i=1}^{n} f_i i! \sum_{j=0}^{i} (-1)^{j} \binom {i - 1} {j} \frac {x^{i-j}} {(i-j)!}$ ，成链答案就是若干个卷起来，成环的话最后还要减去首尾同色的答案。

review

本题中的指数生成函数又称"带容斥系数的生成函数",其关键是考虑广义的二项式反演 $ F(n,m) = \sum_{i,j} (-1)^{n-i+m-j} G(i,j)$ ,正确性可以不断的套一维的二项式反演.

与其类似的,设 $G(n_k) $ 为长度为 $ n $ 的排列,方案数是 $ \frac {n!} {n_1! n_2! .. n_k!} $ ,这一部分用 egf 就可以解决了.再考虑前面的系数,枚举与第一个位置相邻的同色联通块大小,算上此时的贡献.注意为 $ (-1)^{j} $ ,因为当 $ j = 0 $ 时候,贡献是正的,意义是不限制随便排列.

再考虑如何从 $ Seq $ 推到 $ Cyc $ ,对于长度为 $ len $ 的环,在容斥的时候一个合法的方案对应 $ len $ 个 $ Seq $ 的方案,对应位置除以 $ len $ 就可以了. (考虑 $ Seq_k $ 和 $ Cyc_k $ 对应位置的系数).

也可以直接在生成函数里面减去钦定头尾相同的贡献.

巴特西

loj 3102

最新文章

热门文章