[ARC140D] One to One

个人思路：

一棵树也只有一个 \(a=-1\) 的点，所以可以把它看做一个点，但是要记录点的大小 \(sz_i\)，即为这棵树的大小。如果本来就是一个点，那么大小为 \(1\)。

状态：\(dp_{i,j}\) 表示前 \(i\) 个点已确定，已产生 \(j\) 个连通块的方案数。

转移：\(dp_{i,j} = dp_{i-1,j-1} \times sz_i + dp{i-1,j} \times (n-sz_i)\)。

这个状态如果选择了后面的点，会直接影响后面的点的大小，不可做。

然后就不会了。

正解：

设 \(a=-1\) 的点共有 \(m\) 个。

\(k\) 个点 \(x_1,x_2,\dots ,x_k\) 构成一个环，有 \((k-1)! \times \prod\limits_{i=1}^k sz_{x_i}\) 种方案数，因为每个点下一个连接的点形成的排列有 \((k-1)!\) 种，而每个点中有 \(sz_i\) 种选择。

剩下的随便选，每种环在所有方案中出现了 \(n^{m-k}\) 次。那么这 \(k\) 个点构成的环对答案的贡献为 \((k-1)! \times \prod\limits_{i=1}^k sz_{x_i} \times n^{m-k}\)。

显然，我们可以把任选 \(k\) 个点的 \(sz_i\) 乘积之和算出来，可以 \(\Theta(n^2)\) 递推，具体看代码。

巴特西

[ARC140D] One to One

最新文章

热门文章