整理的算法模板合集： ACM模板
点我看算法全家桶系列！！！
实际上是一个全新的精炼模板整合计划
题目链接
https://hydro.ac/d/bzoj/p/2159
是 hydro 的 BZOJ 修复工程 ！（我也去领了一点题慢慢修着玩，这题就是我修的嘿嘿嘿）
Problem
Crash 小朋友最近迷上了一款游戏——文明5 (Civilization V)。在这个游戏中，玩家可以建立和发展自己的国家，通过外交和别的国家交流，或是通过战争征服别的国家。
现在 Crash 已经拥有了一个 n n n 个城市的国家，这些城市之间通过道路相连。由于建设道路是有花费的，因此 Crash 只修建了 n − 1 n-1 n−1 条道路连接这些城市，不过可以保证任意两个城市都有路径相通。
在游戏中，Crash 需要选择一个城市作为他的国家的首都，选择首都需要考虑很多指标，有一个指标是这样的：
S ( i ) = ∑ j = 1 n d i s t ( i , j ) k S(i) = \sum_{j = 1}^{n}{\rm dist}(i, j) ^ k S(i)=j=1∑ndist(i,j)k
其中 S ( i ) S(i) S(i) 表示第 i i i 个城市的指标值， d i s t ( i , j ) {\rm dist}(i, j) dist(i,j) 表示第 i i i 个城市到第 j j j 个城市需要经过的道路条数的最小值， k k k 为一个常数且为正整数。
因此 Crash 交给你一个简单的任务：给出城市之间的道路，对于每个城市，输出这个城市的指标值，由于指标值可能会很大，所以你只需要输出这个数 m o d 10007 \bmod\ 10007 mod 10007 的值。
1 ≤ n ≤ 5 × 1 0 4 1\le n\le 5\times 10^4 1≤n≤5×104 ， 1 ≤ k ≤ 150 1\le k\le 150 1≤k≤150。
Solution
没有边权的无根树^ q ^
当 k = 1 k=1 k=1 时显然是经典的换根DP。
考虑如何处理 d i s t k \mathrm{dist}^k distk。
我们知道第二类斯特林数 S ( n , m ) = { n m } S(n,m)= \left \{ {\begin{matrix} n\\ m \end{matrix}} \right \} S(n,m)={nm} 满足
m n = ∑ i = 0 n { i n } i ! ( m i ) m^{n}=\sum_{i=0}^{n} \left \{ {\begin{matrix} i\\ n \end{matrix}} \right \} i ! {m\choose i} mn=i=0∑n{in}i!(im)
则有：
S x = ∑ i = 1 n d i s ( i , x ) k = ∑ i = 1 n ∑ j = 0 k { k j } ( d i s ( i , x ) j ) j ! = ∑ j = 0 k { k j } j ! ∑ i = 1 n ( d i s ( i , x ) j ) = ∑ j = 0 k { k j } j ! ∑ i = 1 n ( ( d i s ( i , x ) − 1 j ) + ( d i s ( i , x − 1 ) j − 1 ) ) \begin{aligned}S_{x} &=\sum_{i=1}^{n} \mathrm{d i s}(i, x)^{k} \\&=\sum_{i=1}^{n} \sum_{j=0}^{k} \left \{ {\begin{matrix} k\\ j \end{matrix}} \right \} {\mathrm{d i s}(i, x)\choose j}j ! \\&=\sum_{j=0}^{k}\left\{\begin{array}{c}k \\j\end{array}\right\} j ! \sum_{i=1}^{n} {\mathrm{d i s}(i, x)\choose j} \\&=\sum_{j=0}^{k}\left\{\begin{array}{c}k \\j\end{array}\right\} j ! \sum_{i=1}^{n}\left({\mathrm{d i s}(i, x)-1\choose j}+{\mathrm{d i s}(i, x-1)\choose j-1}\right)\end{aligned} Sx=i=1∑ndis(i,x)k=i=1∑nj=0∑k{kj}(jdis(i,x))j!=j=0∑k{kj}j!i=1∑n(jdis(i,x))=j=0∑k{kj}j!i=1∑n((jdis(i,x)−1)+(j−1dis(i,x−1)))
考虑继续做换根DP。
设 f [ x , j ] f[x,j] f[x,j] 表示以 x x x 为根的子树中，上述表达式的后半部分的答案。
显然有转移方程：
f [ x , j ] = ∑ s o n ∈ x _ s o n f [ s o n , j ] + f [ s o n , j − 1 ] f[x,j]=\sum\limits_{\mathrm{son}\in \mathrm{x\_{son}}}f[\mathrm{son}, j]+f[\mathrm{son}, j-1] f[x,j]=son∈x_son∑f[son,j]+f[son,j−1]
预处理之后直接进行换根DP即可。
时间复杂度 O ( n k ) O(nk) O(nk)
Code