当我跨过沉沦的一切
向着永恒开战的时候
你是我的军旗

标签 purfer 序列 下的文章

对于两棵树 T_1, T_2,定义它们的交 T_1 \cap T_2 是它们的边集的交形成的森林,k(T_1 \cap T_2)表示这个森林的连通块个数,求下列三种问题之一:

  1. 给定 T_1, T_2,求 y^{k(T_1\cap T_2)}

  2. 给定 T_1,求 \sum_{T_2}y^{k(T_1\cap T_2)}

  3. 给定 n,求 \sum_{T_1}\sum_{T_2}y^{k(T_1\cap T_2)}

其中 n \leq 10^5 ,上面的 sum 是对所有 n^{n-2} 种可能的树求和。答案对 998244353 取模。

orzrqy

READ MORE

题目要求恰好等于 M 的方案数,我们只需要求出小于等于 M 的和小于等于 M-1 的,相减即可。

考虑 Purfer 序列,他的长度为 N - 2,按照题目要求,每个数只能出现 0 ~ M - 1 次,考虑组合生成函数 f(x) = \sum\limits_{i=0}^{m-1} \frac {x^i} {i!} ,那么答案即 (N-2)![x^{N-2}]f^N(x)

READ MORE