「BZOJ 2159」Crash 的文明世界

Problem

Description

给定一棵树,要求对每个点 u 求出

\sum_{v = 1}^{n}dis(u, v)^{k}

答案对 10007 取模。

Constraints

1\le n\le 5\times 10^{4},1\le k\le 150

Solution

Analysis

第二类斯特林数 (Stirling numbers of the second kind) 套路题。

由于

x^{n}=\sum_{k = 0}^{n}\genfrac{\{}{\}}{0pt}{}{n}{k}x^{\underline{k}}=\sum_{k = 0}^{n}\genfrac{\{}{\}}{0pt}{}{n}{k}\binom{x}{k}k!

对式子进行转化:

\begin{aligned} \sum_{v = 1}^{n}dis(u, v)^{k} &= \sum_{v = 1}^{n}\sum_{i = 0}^{k}\genfrac{\{}{\}}{0pt}{}{k}{i}\binom{dis(u, v)}{i}i!\\ &= \sum_{i = 0}^{k}\genfrac{\{}{\}}{0pt}{}{k}{i}i!\sum_{v = 1}^{n}\binom{dis(u, v)}{i} \end{aligned}

第二类斯特林数与阶乘可以 O\left(k^{2}\right) 求得,考虑式子的后半部分。

f,g

\begin{aligned} f_{u,k} &= \sum_{v\in\operatorname{sub}(u)}\binom{dis(u, v)}{k}\\ g_{u,k} &= \sum_{v\notin\operatorname{sub}(u)}\binom{dis(u, v)}{k} \end{aligned}

则显然有 DP 方程:

\begin{aligned} f_{u, k} &= \sum_{v\in\operatorname{son}(u)}\sum_{w\in\operatorname{sub}(v)}\binom{dis(v, w)+1}{k}\\ &= \sum_{v\in\operatorname{son}(u)}\sum_{w\in\operatorname{sub}(v)}\binom{dis(v, w)}{k}+\binom{dis(v, w)}{k-1}\\ &= \sum_{v\in\operatorname{son}(u)}f_{v, k}+f_{v, k-1}\\ g_{u, k} &= \sum_{v\notin\operatorname{sub}(fa_{u})}\binom{dis(fa_{u}, v)+1}{k}+\sum_{v\in\operatorname{sub}(fa_{u})-\operatorname{sub}(u)}\binom{dis(fa_{u}, v)+1}{k}\\ &= g_{fa_{u}, k} + g_{fa_{u}, k-1} + f_{fa_{u}, k} + f_{fa_{u}, k - 1} - f_{u, k} - 2f_{u, k - 1} - f_{u, k - 2} \end{aligned}

时间复杂度 O\left((n + k)k\right)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<cstdio>

using i64=long long;
using uchar=unsigned char;

constexpr int maxn(50000);
constexpr int maxk(150);
constexpr int p(10007);
constexpr int p4(p<<2);

inline int io(){
static int _;
return scanf("%d",&_),_;
}

struct Edge{
int v;Edge*las;
inline Edge* init(const int&to,Edge*const&ls)
{return v=to,las=ls,this;}
}*las[maxn+1];

inline void lnk(const int&u,const int&v){
static Edge pool[maxn<<1],*alc=pool-1;
las[u]=(++alc)->init(v,las[u]);
las[v]=(++alc)->init(u,las[v]);
}

int f[maxn+1][maxk+1],
g[maxn+1][maxk+1];

const int n(io()),k(io());

void calcf(const int&u,const int&fa){
f[u][0]=1;
for(Edge*o=las[u];o;o=o->las)
if(o->v!=fa){
calcf(o->v,u);
f[u][0]+=f[o->v][0];
for(int i=1;i<=k;++i)
f[u][i]+=f[o->v][i-1]+f[o->v][i];
}
for(int i=0;i<=k;++i)
f[u][i]%=p;
}

void calcg(const int&u,const int&fa){
g[u][0]=(n-f[u][0])%p;

if(fa){
g[u][1]=(g[fa][0]+g[fa][1]+f[fa][0]+f[fa][1]-(f[u][0]<<1)-f[u][1]+p4)%p;
for(int i=2;i<=k;++i)
g[u][i]=(
g[fa][i-1]+g[fa][i]
+f[fa][i-1]+f[fa][i]
-f[u][i-2]-(f[u][i-1]<<1)-f[u][i]
+p4
)%p;
}

for(Edge*o=las[u];o;o=o->las)
if(o->v!=fa)
calcg(o->v,u);
}

int S[maxk+1][maxk+1],
Fac[maxk+1];

int main(){
const int L(io());int t=io();
const int A(io()),B(io()),Q(io());

for(int i=1;i!=L;++i)
t=(t*A+B)%Q,
lnk(i-t%i,i+1);
for(int i=L;i!=n;++i)
t=(t*A+B)%Q,
lnk(i-t%L,i+1);

calcf(1,0);
calcg(1,0);

S[0][0]=Fac[0]=1;
for(int i=1,v=1;i<=k;++i)
for(int j=(Fac[i]=v=(i64)v*i%p,1);j<=i;++j)
S[i][j]=(S[i-1][j-1]+(i64)S[i-1][j]*j)%p;

i64 ans;
for(int u=1;u<=n;++u){
ans=0;
for(int i=1;i<=k;++i)
ans+=(i64)S[k][i]*Fac[i]%p*(f[u][i]+g[u][i])%p;
printf("%d\n",ans%p);
}

return 0;
}