「CTS2019」氪金手游

解题思路

考场上想出了外向树的做法，居然没意识到反向边可以容斥，其实外向树会做的话这个题差不多就做完了。

令 \(dp[u][i]\) 表示单独考虑 \(u\) 节点所在子树，子树内 \(\sum w=i\) 的合法概率，可以简单证明子树外的选取是不影响子树内的答案的，所以可以这样表示。

证明：我们只考虑子树内的第一个选出根节点 \(u\) 的概率是 \(\frac{w_u}{i}\)，假设当前未被选走的卡的概率之和为 \(S\) ，那么考虑全部未被选走的卡，子树内第一个选走 \(u\) 的概率为

\[\dfrac{w_u}{S}\sum_{k=0}^{\infty} (\dfrac{S-i}{S})^k
=\dfrac{w_u}{S}\times\dfrac{1}{1-\frac{S-i}{S}} \\
=\dfrac{w_u}{S} \times \frac{i}{S}= \frac{w_u}{i}
\]

两式相等，得证。

转移比较显然，因为是外向树，所以 \(u\) 要当中第一个被选中，剩下相当于对 \(w\) 做背包，直接从儿子合并即可。

考虑不是一棵外向树对其进行容斥，令 \(G(k)\) 表示有 \(k\) 条反向边被钦点为正向，剩下的反向边可反向也可正向的方案数，那么答案就是 \(\sum_{i=0}^m (-1)^i G(i)\) 。

发现可反向也可正向相当于把这条边删掉，两个连通块贡献用乘法原理合并，然后把容斥系数带到 \(dp\) 转移里面计算即可。

code

/*program by mangoyang*/

#include <bits/stdc++.h>

#define inf (0x7f7f7f7f)

#define Max(a, b) ((a) > (b) ? (a) : (b))

#define Min(a, b) ((a) < (b) ? (a) : (b))

typedef long long ll;

using namespace std;

template <class T>

inline void read(T &x){

	int ch = 0, f = 0; x = 0;

	for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;

	for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;

	if(f) x = -x;

}

const int mod = 998244353;

vector<int> g[1005], d[1005];

int dp[1005][3005], sz[1005], w[1005][4], a[3005], n;

inline void up(int &x, int y){

    x = x + y >= mod ? x + y - mod : x + y;

}

inline int Pow(int a, int b){

    int ans = 1;

    for(; b; b >>= 1, a = 1ll * a * a % mod)

        if(b & 1) ans = 1ll * ans * a % mod;

    return ans;

}

inline void gao(int u, int v, int type){

    for(int i = 1; i <= 3 * sz[u]; i++)

        for(int j = 1; j <= 3 * sz[v]; j++){

            int x = 1ll * dp[u][i] * dp[v][j] % mod;

            if(type) up(a[i], x);

            up(a[i+j], type ? mod - x : x);

        }

    for(int i = 1; i <= 3 * (sz[u] + sz[v]); i++)

        dp[u][i] = a[i], a[i] = 0;

    sz[u] += sz[v];

}

inline void dfs(int u, int fa){

    sz[u] = 1;

    dp[u][1] = w[u][1], dp[u][2] = w[u][2], dp[u][3] = w[u][3];

    for(auto v : g[u])

        if(v != fa) dfs(v, u), gao(u, v, 0);

    for(auto v : d[u])

        if(v != fa) dfs(v, u), gao(u, v, 1);

    for(int i = 1; i <= 3 * sz[u]; i++)

        dp[u][i] = 1ll * dp[u][i] * Pow(i, mod - 2) % mod;

}

int main(){

    read(n);

    for(int i = 1, x, y, z; i <= n; i++){

        read(x), read(y), read(z);

        int s = Pow(x + y + z, mod - 2);

        w[i][1] = 1ll * x * s % mod;

        w[i][2] = 2ll * y * s % mod;

        w[i][3] = 3ll * z * s % mod;

    }

    for(int i = 1, x, y; i < n; i++){

        read(x), read(y);

        g[x].push_back(y);

        d[y].push_back(x);

    }

    dfs(1, 0);

    int ans = 0;

    for(int i = 1; i <= 3 * n; i++) up(ans, dp[1][i]);

    cout << ans << endl;

    return 0;

}

巴特西

「CTS2019」氪金手游

「CTS2019」氪金手游

code

最新文章

热门文章