Description
给定一棵\(n\)个点的树和正整数\(k\),每条边长度都为\(1\),对于每个点\(u\)求:\(\sum_{j=1}^{n}dist(u,j)^k;\) \(n<=50000,k<=150\),答案对\(10007\)取模
Solution
组合数学+树形\(dp\)
- 先给出一个式子:
- \(a^k=\sum_{i=1}^{k}S(k,i)*i!*C(a,i)\)
- 解释:\(a^k\)看作\(k\)个球放入\(a\)个有区别的盒子里的方案数
- \(S(k,i)\)为第二类斯特林数,表示\(k\)个球放入\(i\)个盒子,不允许盒子空着,且这\(i\)个盒子无区别的方案数
- \(i!*C(a,i)\)其实就是\(A(a,i)\)
- 上式即枚举\(i\)个盒子非空,用\(S(k,i)\)乘上a个盒子中,有序选i个的方案数
- 因此原式 \(=\sum_{j=1}^{n}\sum_{i=1}^{k}S(k,i)*i!*C(dist(u,j),i)\)
- 考虑先枚举\(i\),那么原式化为\(\sum_{i=1}^{k}S(k,i)*i!*\sum_{j=1}^{n}C(dist(u,j),i)\)
- 其中\(S(k,i)=S(k-1,i)*i+S(k-1,i-1)\)
- 问题转化为求\(\sum_{j=1}^{n}C(dist(u,j),i)\)
- 考虑树形\(dp\),即将\(j\)按是否在\(u\)子树内分类
- 设\(f[u][i]\)表示\(\sum_{j在u子树内}C(dist(u,j),i)\)
- 众所周知\(C(x,y)=C(x-1,y-1)+C(x-1,y)\)
- 于是枚举\(u\)的每个儿子\(v\)进行递推:
\(f[u][i]+=\sum_{j在v子树内}C(dist(v,j),i)+C(dist(v,j),i-1)\) - 即\(f[u][i]+=f[v][i]+f[v][i-1]\)
- 注意特判\(f[u][0]+=f[v][0]\),即\(i=0\)的时候不要\(+=f[v][i-1]\)
- 设\(g[u][i]\)表示\(\sum_{j=1}^{n}C(dist(u,j),i)\)
- 枚举\(u\)的每个儿子\(v\)
- 能给\(g[v][i]\)贡献的部分即\(\sum_{j不在v子树中}C(dist(u,j),i)\) ,记为\(now[i]\)
- 显然\(now[i]=g[u][i]-f[v][i-1]-f[v][i]\)
- 再递推到\(v\)即\(g[v][i]=f[v][i]+now[i]+now[i-1]\)
- 与上文\(f[u][0]\)同理,注意特判\(g[v][0]\)
Code
#include <bits/stdc++.h>
using namespace std;
template <class t>
inline void read(t & res)
{
char ch;
while (ch = getchar(), !isdigit(ch));
res = ch ^ 48;
while (ch = getchar(), isdigit(ch))
res = res * 10 + (ch ^ 48);
}
const int e = 50005, o = 155, mod = 10007;
int n, m, f[e][o], g[e][o], now[o], s[o][o], adj[e], nxt[e * 2], go[e * 2], num, fac[o];
inline void link(int x, int y)
{
nxt[++num] = adj[x];
adj[x] = num;
go[num] = y;
nxt[++num] = adj[y];
adj[y] = num;
go[num] = x;
}
inline void add(int &x, int y)
{
x += y;
while (x >= mod) x -= mod;
}
inline void dfs1(int u, int pa)
{
int i, j;
f[u][0] = 1;
for (i = adj[u]; i; i = nxt[i])
{
int v = go[i];
if (v == pa) continue;
dfs1(v, u);
add(f[u][0], f[v][0]);
for (j = 1; j <= m; j++) add(f[u][j], f[v][j - 1] + f[v][j]);
}
for (j = 0; j <= m; j++) g[u][j] = f[u][j];
}
inline void dfs2(int u, int pa)
{
int i, j;
for (i = adj[u]; i; i = nxt[i])
{
int v = go[i];
if (v == pa) continue;
for (j = 0; j <= m; j++) now[j] = g[u][j];
add(now[0], mod - f[v][0]);
for (j = 1; j <= m; j++) add(now[j], 2 * mod - f[v][j] - f[v][j - 1]);
add(g[v][0], now[0]);
for (j = 1; j <= m; j++) add(g[v][j], now[j - 1] + now[j]);
dfs2(v, u);
}
}
int main()
{
int i, j, x, y;
read(n); read(m);
for (i = 1; i < n; i++)
{
read(x);
read(y);
link(x, y);
}
fac[0] = 1;
for (i = 1; i <= m; i++) fac[i] = fac[i - 1] * i % mod;
for (i = 1; i <= m; i++)
for (j = 1; j <= i; j++)
if (j == 1) s[i][j] = 1;
else s[i][j] = (s[i - 1][j] * j + s[i - 1][j - 1]) % mod;
dfs1(1, 0);
dfs2(1, 0);
for (i = 1; i <= n; i++)
{
int ans = 0;
for (j = 1; j <= m; j++) add(ans, 1ll * s[m][j] * fac[j] * g[i][j] % mod);
printf("%d\n", ans);
}
return 0;
}