题解：【CTS2019】P5405 氪金手游

· · 题解

题目大意

给定 N 个点，第 i 个点会有一个权值 W_i\in[1,3]，其中 W_i=j 的概率为

p_{i,j}=\frac{a_{i,j}}{a_{i,1}+a_{i,2}+a_{i,3}}

接下来你要生成一个长度为 N 的排列，其中点 i 被选中并放入排列中的概率为 \dfrac{W_i}{\sum W}。

令 i 在排列中的位置为 T_i，下面有 N-1 个二元限制 (u_i,v_i) 满足对于任意的 \varnothing\ne S\subsetneqq\{1,2,\cdots,N\} 都存在至少一对 (u_i,v_i) 使得 u_i\in S,v_i\notin S 或 u_i\notin S,v_i\in S。请求出生成满足对于所有 i 均有 T_{u_i}<T_{v_i} 的排列的概率模上 998244353 的值。

数据范围：N\le 10^3,a_{i,j}\le 10^6。

解题思路

首先容易发现，若从 u_i 向 v_i 连一条有向边，则所有 N-1 对二元组 (u_i,v_i) 构成了一棵有向树，因为其满足从 N 个点中任选一个子点集，都存在点集中的一点与点集外的一点有边, 故该图为简单有向连通图。又因为边数为 N-1，故该图形成一棵有向树。

一棵有向树不太好处理，所以先考虑特殊情况下如何处理。不妨先考虑外向树（即所有边均为父亲连向儿子）的做法，则此时父亲在排列中的位置必须严格在它的所有儿子之前，问题就转化为：求生成满足所有父亲在排列中的位置均严格在其所有儿子之前的排列的概率。

这个问题的做法是容易的。令一个点 u 的儿子为 v，则 T_u<T_v 的概率为

P(u)=\frac{W_u}{\sum W}\sum_{k=0}^\infty\left(\frac{\sum W-W_u}{\sum W}\right)^k

其中无穷级数前的部分表示选择 u 的概率，而 \displaystyle\left(\frac{\sum W-W_u}{\sum W}\right)^k 表示 T_u=k+1 时前面 k 个位置选择其它点的概率。然后将其化简得

P(u)=\frac{W_u}{\sum_{v\in{\textrm{subtree}_u}} W_v}

所以 P(u) 的值只与它自己和儿子的 W 值有关，于是就可以使用树上背包。设 f_{i,j} 表示目前处理到第 i 个点，\sum_{v\in{\textrm{subtree}_i}} W_v=j 时的概率，则有转移

f_{i,j}\leftarrow\sum_{k=1}^j f_{i,k}\cdot f_{v,j-k}

初值即为 f_{i,j}=p_{i,j}j~(j\in[1,3])，计算完后所有 f_{i,j} 除以 j 即可，答案即为 \sum_{i=1}^{3N}f_{1,i}。

下面考虑加入反向边的情况。通过容斥容易发现，加入一条反向边 (v_i,u_i) 的概率为不加入这条边的概率减去加入 (u_i,v_i) 的概率。转移与上面类似，不再赘述。时间复杂度为 O\left(N^2\right)。

AC 代码

#include <bits/stdc++.h>
#define ll long long
#define R register
using namespace std; inline int read() {int x=0,f=1; char c=getchar();
while(c<48 || c>57) {if(c=='-') f=-1; c=getchar();} while(c>47 && c<58)
x=(x<<1)+(x<<3)+c-48, c=getchar(); return x*f;} inline void write(ll x)
{static int st[41]; int tp=0; if(x<0) putchar('-'), x=-x; do st[tp++]=x%10,
x/=10; while(x); while(tp) putchar(st[--tp]+48);} int n,a[1001][3],u,v,
lst1[1001],lst2[1001],cnt1,cnt2,s[1001]; ll f[1001][3001],res[3001],ans;
const int mod=998244353; struct edge {int u,v;} e1[1001],e2[1001];
void add(edge e[], int lst[], int &cnt, int u, int v) {e[++cnt]={lst[u],v};
lst[u]=cnt;} int inv(ll x) {int y=mod-2; ll res=1; while(y)
{if(y&1) res=res*x%mod; x=x*x%mod; y>>=1;} return res;}

void chk(int u, int v, bool t)
{
    for(R int j=1; j<=s[u]*3; ++j)
    {
        for(R int k=1; k<=s[v]*3; ++k)
        t?res[j]=(res[j]+f[u][j]*f[v][k])%mod:0,
        res[j+k]=(res[j+k]+(t?-1:1)*f[u][j]*f[v][k]%mod+mod)%mod;
    }

    for(R int j=1; j<=(s[u]+s[v])*3; ++j)
    f[u][j]=res[j], res[j]=0; s[u]+=s[v];
}

void dfs(int x, int y)
{
    ll t=inv(a[x][0]+a[x][1]+a[x][2]); f[x][1]=a[x][0]*t%mod;
    f[x][2]=(a[x][1]*t<<1)%mod; f[x][3]=a[x][2]*t*3%mod; s[x]=1;
    for(R int i=lst1[x]; i; i=e1[i].u) {if(e1[i].v!=y) dfs(e1[i].v,x),
    chk(x,e1[i].v,0);} for(R int i=lst2[x]; i; i=e2[i].u)
    {if(e2[i].v!=y) dfs(e2[i].v,x), chk(x,e2[i].v,1);}
    for(R int i=1; i<=s[x]*3; ++i) f[x][i]=f[x][i]*inv(i)%mod;
}

int main()
{
    n=read(); for(R int i=1; i<=n; ++i) a[i][0]=read(),
    a[i][1]=read(), a[i][2]=read(); for(R int i=1; i<n; ++i)
    u=read(), v=read(), add(e1,lst1,cnt1,u,v),
    add(e2,lst2,cnt2,v,u); dfs(1,0); for(R int i=1; i<=n*3; ++i)
    ans=(ans+f[1][i])%mod; write(ans); return 0;
}