P6862 [RC-03] 随机树生成器
原题
首先考虑\(dp\)的朴素做法，设\(dp_i\)表示\(i\)个点的树时的答案
容易得到：
\[\begin{align}
dp_K &=
\begin{cases}
(K - 1)! &(K \neq 1) \\
0 &(K = 1)
\end{cases} \\
dp_i &= dp_{i-1} \times (i-1) + (i - 2)!
\end{align}
\]
其中\((i-2)!\)表示\(i-1\)个点的满足题目构造条件的树的方案数
这么做的复杂度为\(O(Tn)\)，显然过不了，也没发现什么明显的优化方法，寄
我们转念一想，发现这个题目似乎如果换成计算期望的话会好做非常多
首先还是先考虑期望时的\(dp\)做法，设\(dp_i\)表示\(i\)个点的树时的答案
容易得到：
\[\begin{align}
dp_K &= [K \neq 1] \\
dp_i &= dp_{i-1} + \frac{1}{i-1}
\end{align}
\]
我们发现这个很好优化，明显可以写成通向公式：
\[\begin{align}
E &= \sum_{K+1}^{n}{\frac{1}{i-1}} + 1 \\
&= \sum_{K}^{n-1}{\frac{1}{i}} + 1
\end{align}
\]
我们只需要预处理出\(\sum{\frac{1}{i}}\)的前缀和即可
但还没有结束，因为我们要求的并不是期望，而是答案之和
但是可以知道\(E = \frac{sum}{cnt}\)，其中\(sum\)表示答案之和，\(cnt\)表示方案数
因此我们可以得出\(sum = E \times cnt\)，我们再考虑答案个数怎么求
显然，答案个数就是构造\(n\)个点的树的方案数，即\((n-1)!\)
因此我们只需要预处理出阶乘和逆元的前缀和即可\(O(1)\)查询
总复杂度\(O(n+T)\)