M_sea

洛谷5405 [CTS2019]氪金手游
LuoguLOJ分析大概是 CTS2019 中最简单的一题?然而我还是不会做首先考虑一棵外向树的情况。假设现在在考...
扫描右侧二维码阅读全文
16
2019/07

洛谷5405 [CTS2019]氪金手游

Luogu

LOJ

分析

大概是 CTS2019 中最简单的一题?然而我还是不会做


首先考虑一棵外向树的情况。

假设现在在考虑子树 $i$ ,设其子树中所有点的 $w_i$ 的和为 $sw$ ,整棵树上所有点的 $w_i$ 的和为 $s$ 。

可以推出 $i$ 比子树中所有点都要早抽到的概率为

$$ \displaystyle\frac{w_i}{s}\sum_{i=0}^n\left(\frac{s-sw}{s}\right)^i $$

化简一下得到

$$ \displaystyle\frac{w_i}{sw} $$

这个东西之和子树信息有关,可以树形 DP 计算。

设 $f_{i,j}$ 表示 $i$ 子树中权值和为 $j$ 的概率和。转移就是树形背包。

这样子可以得到 $0$ 分的好成绩。


现在加入了反向边,考虑把反向边容斥掉,也就是令这些边不存在或者反向。

直接枚举反向边的状态,然后在形成的外向森林上 DP 即可。

时间复杂度 $O(2^nn^2)$ ,可以获得 $20$ 分的好成绩。


进一步发现,我们不需要知道每条反向边的状态,只需要有多少条反向边被反向掉了即可。

考虑把这个东西丢到状态里去。设 $f_{i,j,k}$ 表示 $i$ 子树中权值和为 $j$ ,有 $k$ 条反向边被反向了的概率和。

转移还是树形背包。时间复杂度 $O(n^3)$ ,可以获得 $50$ 分的好成绩。


再进一步发现,我们没有必要加上 $k$ 这一维来计算容斥系数,只需要在转移时顺便乘上容斥系数即可。

具体的,如果反向了一条反向边,就把 DP 值乘上 $-1$ 即可。


具体实现的话,可以给每条边记一个边权,$0$ 表示正向边,$1$ 表示反向边,然后每个条件连两条边即可。

细节见代码。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1000+10;
const int mod=998244353;

inline int qpow(int a,int b) {
    int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod)
        if (b&1) c=1ll*c*a%mod;
    return c;
}

struct edge { int v,w,nxt; } e[N<<1];
int head[N];

inline void addEdge(int u,int v,int w) {
    static int cnt=0;
    e[++cnt]=(edge){v,w,head[u]},head[u]=cnt;
}

int n;
int a[N],b[N],c[N],p[N];
int sz[N];
int f[N][3*N],tmp[3*N];

inline void dfs(int u,int fa) {
    sz[u]=1;
    f[u][1]=1ll*a[u]*p[u]%mod;
    f[u][2]=2ll*b[u]*p[u]%mod;
    f[u][3]=3ll*c[u]*p[u]%mod;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==fa) continue;
        dfs(v,u);
        for (re int j=1;j<=3*sz[u];++j)
            for (re int k=1;k<=3*sz[v];++k) {
                int now=1ll*f[u][j]*f[v][k]%mod;
                if (!e[i].w) tmp[j+k]=(tmp[j+k]+now)%mod;
                else {
                    tmp[j+k]=(tmp[j+k]-now+mod)%mod;
                    tmp[j]=(tmp[j]+now)%mod;
                }
            }
        sz[u]+=sz[v];
        for (re int j=1;j<=3*sz[u];++j) f[u][j]=tmp[j];
        for (re int j=1;j<=3*sz[u];++j) tmp[j]=0;
    }
    for (re int i=1;i<=3*sz[u];++i)
        f[u][i]=1ll*f[u][i]*qpow(i,mod-2)%mod;
}

int main() {
    n=read();
    for (re int i=1;i<=n;++i) {
        a[i]=read(),b[i]=read(),c[i]=read();
        p[i]=qpow(a[i]+b[i]+c[i],mod-2);
    }
    for (re int i=1;i<n;++i) {
        int u=read(),v=read();
        addEdge(u,v,0),addEdge(v,u,1);
    }
    dfs(1,0);
    int ans=0;
    for (re int i=1;i<=3*n;++i) ans=(ans+f[1][i])%mod;
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 07 月 16 日 09 : 30 PM

发表评论