CTS2019 氪金手游

link

如果所有边都指向根的方向,那么就是要求每个点在子树中所有点之前,

所以考虑子树的$w_i$和 和$w_x$($x$是子树根),那么概率就是$\frac{w_x}{\sum w_i}$

当然$w_i$也包含$w_x$

这东西可以DP f[x][y]表示以$x$为根,子树$w_i$和为$y$ 满足条件的概率。

如果有反向边,那么容斥是否不满足,如果不满足则为正向边,否则就不管这条边(对子树大小的贡献)

容易看出有$k$条反边不满足的贡献是$(-1)^k$,所以就可以直接类似的DP了

code version1:

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
const int p=998244353;
int a[1005][4];
int fpm(int a,int b){
int c=1;
for(;b;b>>=1,a=a*a%p)if(b&1)c=c*a%p;
return c;
}
int inv[3005];
vector<pii> to[1005];
int f[1005][3005],siz[3005];
int g[3005],h[3005];
int cnt[1005];
void dfs(int x,int fa){
for(auto i:to[x])if(i.x!=fa){
dfs(i.x,x);
}
for(int j=1;j<=3;++j){
int s=0;
g[0]=1;
for(auto i:to[x])if(i.x!=fa){
for(int x=0;x<=s;++x){
if(i.y)h[x]=(h[x]+g[x]*cnt[i.x])%p;
for(int y=0;y<=siz[i.x];++y)
if(i.y)
h[x+y]=(h[x+y]-g[x]*f[i.x][y]%p+p)%p;
else
h[x+y]=(h[x+y]+g[x]*f[i.x][y]%p)%p;
}
for(int x=0;x<=s+siz[i.x];++x){g[x]=h[x];h[x]=0;}
s+=siz[i.x];
}
for(int i=0;i<=s;++i)f[x][i+j]=(f[x][i+j]+g[i]*a[x][j]%p*j*inv[i+j])%p;
chkmax(siz[x],s+j);
}
for(int i=0;i<=siz[x];++i)cnt[x]=(cnt[x]+f[x][i])%p;
}
signed main(){
#ifdef QAQAutoMaton
freopen("fgo.in","r",stdin);
freopen("fgo.out","w",stdout);
#endif
int n;
read(n);
inv[1]=1;
for(int i=2;i<=n*3;++i){
inv[i]=(p-p/i)*inv[p%i]%p;
}
for(int i=1;i<=n;++i){
read(a[i][1]);
read(a[i][2]);
read(a[i][3]);
int w=fpm(a[i][1]+a[i][2]+a[i][3],p-2)%p;
a[i][1]=a[i][1]*w%p;
a[i][2]=a[i][2]*w%p;
a[i][3]=a[i][3]*w%p;
}
int u,v;
for(int i=1;i<n;++i){
read(u,v);
to[u].push_back(make_pair(v,0));
to[v].push_back(make_pair(u,1));
}
dfs(1,0);
int ans=0;
for(int i=0;i<=n*3;++i)ans=(ans+f[1][i])%p;
write(ans,'\n');
return 0;
}

code version2:

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
const int p=998244353;
int a[1005][4];
int fpm(int a,int b){
int c=1;
for(;b;b>>=1,a=a*a%p)if(b&1)c=c*a%p;
return c;
}
int inv[3005];
vector<pii> to[1005];
int f[1005][3005],siz[3005];
int g[3005],h[3005];
int cnt[1005];
void dfs(int x,int fa){
for(auto i:to[x])if(i.x!=fa)dfs(i.x,x);
int s=3;
g[0]=0;
g[1]=a[x][1];
g[2]=a[x][2]*2%p;
g[3]=a[x][3]*3%p;
for(auto i:to[x])if(i.x!=fa){
for(int x=0;x<=s;++x){
if(i.y)h[x]=(h[x]+g[x]*cnt[i.x])%p;
for(int y=0;y<=siz[i.x];++y)
if(i.y)
h[x+y]=(h[x+y]-g[x]*f[i.x][y]%p+p)%p;
else
h[x+y]=(h[x+y]+g[x]*f[i.x][y]%p)%p;
}
for(int x=0;x<=s+siz[i.x];++x){g[x]=h[x];h[x]=0;}
s+=siz[i.x];
}
for(int i=0;i<=s;++i)f[x][i]=g[i]*inv[i]%p;
siz[x]=s;
for(int i=0;i<=siz[x];++i)cnt[x]=(cnt[x]+f[x][i])%p;
}
signed main(){
#ifdef QAQAutoMaton
freopen("fgo.in","r",stdin);
freopen("fgo.out","w",stdout);
#endif
int n;
read(n);
inv[1]=1;
for(int i=2;i<=n*3;++i){
inv[i]=(p-p/i)*inv[p%i]%p;
}
for(int i=1;i<=n;++i){
read(a[i][1]);
read(a[i][2]);
read(a[i][3]);
int w=fpm(a[i][1]+a[i][2]+a[i][3],p-2)%p;
a[i][1]=a[i][1]*w%p;
a[i][2]=a[i][2]*w%p;
a[i][3]=a[i][3]*w%p;
}
int u,v;
for(int i=1;i<n;++i){
read(u,v);
to[u].push_back(make_pair(v,0));
to[v].push_back(make_pair(u,1));
}
dfs(1,0);
int ans=0;
for(int i=0;i<=n*3;++i)ans=(ans+f[1][i])%p;
write(ans,'\n');
return 0;
}

# DP

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×