# yukicoder No.1302 Random Tree Score

FPSライブラリを使わず式変形で解く方法

## 問題リンク
- https://yukicoder.me/problems/no/1302

## 解法
まず, 公式解説と同様にして, 形式的べき級数
$$ F=\sum_{n=1}^{\infty}{\frac{n}{(n-1)!}x^n}$$
により答えを
$$\frac{(N-2)!}{N^{N-2}}[x^{2(N-1)}]F^N$$
と表します. $\frac{(N-2)!}{N^{N-2}}$ の部分は $O(N)$ 時間で求められるので $F^N$ の係数を取り出す方法が分かればこの問題が解けます.

$\frac{F}{x}$ について

$$\begin{aligned}
\int \frac{F}{x} &=\sum_{n=1}^{\infty} \int \frac{n}{(n-1)}x^{n-1} \\
&= \sum_{n=1}^{\infty}{\frac{1}{(n-1)!}x^n} \\
&= x\sum_{n=0}^{\infty}{\frac{1}{n!}x^n} \\
&= xe^x (\because e^x=\sum_{n=0}^{\infty}{\frac{1}{n!}x^n})
\end{aligned}
$$
ですから, 両辺微分することで
$$ \frac{F}{x} = (x+1)e^x$$
となり
$$ F=x(x+1)e^x$$
が得られます. これにより $$F^N=x^N(x+1)^Ne^{Nx}$$ とわかります.
以上より
$$
\begin{align}
[x^{2(N-1)}]F^N
&= [x^{N-2}]\left(x+1\right)^Ne^{Nx} \\
&= \sum_{i=0}^{N}{\left([x^i](x+1)^N\right)\left([x^{N-i-2}]e^{Nx}\right)} \\
&= \sum_{i=0}^{N}{\binom{N}{i}\frac{N^{N-i-2}}{(N-i-2)!}}
(\because e^{Nx}=\sum_{n=0}^{\infty}{\frac{N^n}{n!}x^n})
\end{align}
$$
でありこれは $O(N\log N)$で計算可能です.
したがってこの問題を $O(N\log N)$ で解けました.