目录
补题情况
| 题目 | 蒋贤蒙 | 王赵安 | 王智彪 |
|---|---|---|---|
| A | 0 | 0 | 0 |
| B | 2 | 0 | 2 |
| C | 2 | 0 | 1 |
| D | 2 | 1 | 0 |
| E | 2 | 0 | 1 |
| F | 2 | 0 | 2 |
| G | 2 | 0 | 2 |
| H | 0 | 1 | 2 |
| I | 2 | 0 | 2 |
| J | 2 | 0 | 2 |
题解
D. Rebuild Tree
题意
给定一棵树，要求删除 $k$ 条边再补上 $k$ 条边，使得新图仍然是一棵树，问方案数。
题解
首先删除 $k$ 条边得到 $k+1$ 个连通块，设第 $i$ 个连通块有 $s_i$ 个点。
固定 $(s_1,s_2\cdots s_{k+1})$，将每个连通块缩点后构造 $\text{prufer}$ 序列。设第 $i$ 个连通块在新图中得度数为 $d_i$，知每个生成树的贡献为
$$ \prod_{i=1}^{k+1}s_i^{d_i} $$
设 $p_i$ 表示第 $i$ 个连通块在 $\text{prufer}$ 序列中出现的次数，根据 $\text{prufer}$ 序列性质，知 $d_i=p_i+1$，于是有
$$ \prod_{i=1}^{k+1}s_i^{d_i}= \left(\prod_{i=1}^{k+1}s_i\right)\left(\prod_{i=1}^{k+1}s_i^{p_i}\right) $$
考虑 $\prod_{i=1}^{k+1}s_i^{p_i}$ 在 $\text{prufer}$ 序列中的实际意义。
不难发现设 $\text{prufer}$ 序列的权值为每个元素 $a_i$ 按权值 $s_{a_i}$ 相乘之积，则所有 $\prod_{i=1}^{k+1}s_i^{p_i}$ 之和等价于所有 $\text{prufer}$ 序列的权值之和。
不难发现，所有 $\text{prufer}$ 序列的权值之和(固定其他位置，枚举单个位置的变化)等于
$$ \left(\sum_{i=1}^{k+1} s_i\right)^{k-1}=n^{k-1} $$
于是对固定 $(s_1,s_2\cdots s_{k+1})$，总贡献为
$$ \left(\prod_{i=1}^{k+1}s_i\right)\sum_{Tree(k+1)}\left(\prod_{i=1}^{k+1}s_i^{p_i}\right)=\left(\prod_{i=1}^{k+1}s_i\right)\left(\sum_{i=1}^{k+1} s_i\right)^{k-1}=\left(\prod_{i=1}^{k+1}s_i\right)n^{k-1} $$
接下来考虑 $(s_1,s_2\cdots s_{k+1})$ 不固定时产生的总贡献。
不难发现 $\prod_{i=1}^{k+1}s_i$ 等于连通块的大小之积，这可以转化为在每个连通块中选一个点的方案数。
于是设 $\text{dp}(u,k,0/1)$ 表示以 $u$ 为子树已经割 $k$ 条边，$0/1$ 表示 $u$ 所在的连通块是否已经选择代表节点的方案数。
进行树形 $\text{dp}$ 转移，枚举是否割断 $u$ 与 $v\in \text{son}(u)$ 的连边的贡献，注意如果 $v$ 所在的连通块没有代表节点，则 $u\to v$ 一定不可割。
时间复杂度 $O(nk)$。
G. Product
题意
给定 $n,k,D$，求
$$ \sum_{\sum a_i=D,a_i\ge 0}\frac {D!}{\prod_{i=1}^n (a_i+k)} $$
题解
不妨设 $b_i=a_i+k$
$$ \sum_{\sum a_i=D,a_i\ge 0}\frac {D!}{\prod_{i=1}^n (a_i+k)}=\frac {D!}{(D+nk)!}\sum_{\sum b_i=D+nk,b_i\ge k}\frac {(D+nk)!}{\prod_{i=1}^n b_i} $$
不难发现，式子右半部分的组合意义是由元素 $1\sim n$ 构成的长度为 $D+nk$ 的排列个数，其中每个元素出现次数不小于 $k$。
不妨考虑容斥，设 $\text{dp}(i,j)$ 表示由元素 $1\sim i$ 构成的长度为 $j$ 的排列个数，其中每个元素出现次数小于 $k$，不难得到状态转移
$$ \text{dp}(i,j)=\sum_{v=0}^{\min(j,k)}{j\choose v}\text{dp}(i-1,j-v) $$
同时有公式 $n$ 种元素出现次数无限制时构成的长度为 $k$ 的排列个数为 $n^k$，于是有
$$ \sum_{\sum b_i=D+nk,b_i\ge k}\frac {(D+nk)!}{\prod_{i=1}^n b_i}=\sum_{i=0}^n (-1)^n\sum_{j=0}^{ik}{D+nk\choose j}\text{dp}(i,j)(n-i)^{D+nk-j} $$
总时间复杂度 $O\left(n^2k^2\right)$。
