Waiting for the end.
递推式
\[\begin{aligned}
\begin{Bmatrix}n\\k \end{Bmatrix}=\begin{Bmatrix}n-1\\k-1\end{Bmatrix}+k\cdot \begin{Bmatrix}n-1\\k \end{Bmatrix}\\
\begin{bmatrix}n\\k \end{bmatrix}=\begin{bmatrix}n-1\\k-1 \end{bmatrix}+(n-1)\cdot \begin{bmatrix}n-1\\k \end{bmatrix}
\end{aligned}
\]
与上升幂下降幂的关系
\[C_n^kk!=n^{\underline k}\\
\Rightarrow \displaystyle n^m=\sum_{k=0}^m\begin {Bmatrix}m\\k \end{Bmatrix}C_n^kk!=\sum_{k=0}^m\begin {Bmatrix}m\\k \end{Bmatrix}n^{\underline k}\\
\]
\[\displaystyle x^{\overline{n}}=\sum_k \begin{bmatrix}n\\k \end{bmatrix}x^k
\]
可以归纳法证明上式。
反演
\[\displaystyle f(n)=\sum_{k=0}^n \begin{Bmatrix}n\\k \end{Bmatrix}g(k)
\Longleftrightarrow g(n)=\sum_{k=0}^n(-1)^{n-k}\begin {bmatrix} n\\k \end{bmatrix}f(k)
\]
首先有 \((-1)^n(-x^{\underline n}) = x^{\underline n}\) ，这个直接打开化简就可以得到。同理可以有 \((-1)^n(-x^{\overline n}) = x^{\overline n}\) 。
于是带入 \(\displaystyle x^{\overline{n}}=\sum_k \begin{bmatrix}n\\k \end{bmatrix}x^k\) 得到下式
\[\begin{aligned}
\displaystyle n^m&=\sum_{k=0}^{m}\begin{Bmatrix}m\\k\end{Bmatrix}(-1)^k(-n)^{\overline{k}}\\
&=\sum_{k=0}^{m}\begin{Bmatrix}m\\k\end{Bmatrix}(-1)^k\sum_{j=0}^k\begin{bmatrix}k\\j\end{bmatrix}(-n)^j\\
&=\sum_{j=0}^mn^j\sum_{k=j}^{m}\begin{Bmatrix}m\\k\end{Bmatrix}\begin{bmatrix}k\\j\end{bmatrix}(-1)^{k-j}
\end{aligned}
\]
于是得到了
\[\begin{aligned}
\displaystyle \sum_{k=m}^n (-1)^{n-k}\begin{bmatrix}n\\k\end{bmatrix} \begin{Bmatrix}k\\m\end{Bmatrix}=[m=n]\\
\sum_{k=m}^n (-1)^{n-k}\begin{Bmatrix}n\\k\end{Bmatrix} \begin{bmatrix}k\\m\end{bmatrix}=[m=n]
\end{aligned}
\]
下面的式子是同理能得到的。
于是有
\[\begin{aligned}
\displaystyle
g(n)&=\sum_{j=0}^n(-1)^{n-j}\begin{bmatrix}n\\j\end{bmatrix}f(j)\\
\Rightarrow f(n)&=\sum_{j=0}^n[j=n]f(j)\\
&=\sum_{j=0}^n\sum_{k=j}^n\begin{Bmatrix}n\\k\end{Bmatrix}\begin{bmatrix}k\\j\end{bmatrix}(-1)^{k-j}f(j)\\
&=\sum_{k=0}^n\begin{Bmatrix}n\\k\end{Bmatrix}\sum_{j=0}^k(-1)^{k-j}\begin{bmatrix}k\\j\end{bmatrix}f(j)\\
&=\sum_{k=0}^n\begin{Bmatrix}n\\k\end{Bmatrix} g(k)
\end{aligned}
\]
Crash 的文明世界
\[\begin{aligned}
S(u) &= \sum_{v = 1}^{n} \mathrm{dist}(u, v)^{k} \\
&= \sum_{v = 1}^{n} \sum_{i = 0}^{k} \begin{Bmatrix} k \\ i \end{Bmatrix} \binom{\mathrm{dist}(u, v)}{i}i! \\
&= \sum_{i = 0}^{k} \begin{Bmatrix} k \\ i \end{Bmatrix} i! \sum_{v = 1}^{n} \binom{\mathrm{dist}(u, v)}{i}
\end{aligned}
\]
令 \(dp_{u, i} = \sum_{v \in subtree(u)} \binom{\mathrm{dist}(u, v)}{i}\) 。
\[\begin{aligned}
\sum_{v \in subtree(u)} \binom{\mathrm{dist}(u, v)}{i} &= \sum_{v \in subtree(u)} \binom{\mathrm{dist}(u, v) - 1}{i} + \binom{\mathrm{dist}(u, v) - 1}{i - 1} \\
&= \sum_{v \in son(u)} dp_{v, i} + dp_{v, i - 1}
\end{aligned}
\]
Summary
\[n^k = \sum_{i = 1}^{k} \begin{Bmatrix} k \\ i \end{Bmatrix} i! \binom{n}{i}
\]
Crash 的文明世界
\[\begin{aligned}
S(u) &= \sum_{v = 1}^{n} \mathrm{dist}(u, v)^{k} \\
&= \sum_{v = 1}^{n} \sum_{i = 0}^{k} \begin{Bmatrix} k \\ i \end{Bmatrix} \binom{\mathrm{dist}(u, v)}{i}i! \\
&= \sum_{i = 0}^{k} \begin{Bmatrix} k \\ i \end{Bmatrix} i! \sum_{v = 1}^{n} \binom{\mathrm{dist}(u, v)}{i}
\end{aligned}
\]
令 \(dp_{u, i} = \sum_{v \in subtree(u)} \binom{\mathrm{dist}(u, v)}{i}\) 。
\[\begin{aligned}
\sum_{v \in subtree(u)} \binom{\mathrm{dist}(u, v)}{i} &= \sum_{v \in subtree(u)} \binom{\mathrm{dist}(u, v) - 1}{i} + \binom{\mathrm{dist}(u, v) - 1}{i - 1} \\
&= \sum_{v \in son(u)} dp_{v, i} + dp_{v, i - 1}
\end{aligned}
\]
CF932E
\[\begin{aligned}
&\sum_{i = 1}^{n} \binom{n}{i} i^k \\
=&\sum_{i = 1}^{n} \binom{n}{i} \sum_{j = 1}^{k} \begin{Bmatrix} k \\ j \end{Bmatrix} j! \binom{i}{j} \\
=&\sum_{j = 1}^{k} \begin{Bmatrix} k \\ j \end{Bmatrix} j! \sum_{i = j}^{n} \binom{n}{i} \binom{i}{j} \\
=&\sum_{j = 1}^{k} \begin{Bmatrix} k \\ j \end{Bmatrix} j! \sum_{i = j}^{n} \binom{n}{j} \binom{n - j}{i - j} \\
=&\sum_{j = 1}^{k} \begin{Bmatrix} k \\ j \end{Bmatrix} j! \binom{n}{j} \sum_{i = 0}^{n - j} \binom{n}{i} \\
=&\sum_{j = 1}^{k} \begin{Bmatrix} k \\ j \end{Bmatrix} j! \binom{n}{j} 2^{n - j} \\
\end{aligned}
\]
可以 \(\Theta(k^2 + k \log n)\) 。