抱歉，您的浏览器无法访问本站

本页面需要浏览器支持（启用）JavaScript


了解详情 >

AutumnKite's Blog

博客

归档

友链

关于

说说

留言

「模拟赛20190705 T1」第一题

This is a picture without description

AutumnKite
题解模拟赛

发布于：2019年7月7日
次浏览

题意

给定一棵 \(n\) 个点的有根树，每个点有一个正整数\(b_i\)，这个点的权值是 \([0,b_i]\) 的一个随机实数。

求每个点的权值严格小于这个点所有儿子的权值的概率，模 \(10^9+7\)。

\(n\le 300,b_i\le 10^9\)。

所谓题解

This is a picture without description

旺仔的方法

考虑暴力。实数显然不能直接枚举。然而 \(b_i\) 只有 \(n\) 个，我们考虑离散，枚举每个点的权值在哪一段内。

我们按权值所属段是否相同分出一些联通块。树上的联通块还是一棵树，我们考虑求出每个联通块内部的概率。

由于一个联通块内的权值都属于同一段，也就是权值取值范围相同，那么问题转化成了：

给定一棵树，每个点的权值是 \([0,1)\) 的随机实数，求每个点权值严格小于这个点每个儿子的权值的概率。

这个问题是一个经典问题，答案是 \(\prod\limits_{i=1}^{n} \frac{1}{sz_i}\)，可以感性理解一下。我不会证明

枚举每个点太慢，我们考虑 DP。用 \(dp_{i,j,k}\) 表示以 \(i\) 为根的子树，\(i\) 的取值范围为 \(j\)，以 \(i\) 为根的联通块大小为 \(k\) 时的概率。可以通过枚举每个儿子的取值范围是否与 \(i\) 相同，枚举每个儿子的联通块大小进行转移。

相当于 \(n\) 次树上背包，每次 \(O(n^2)\)，复杂度为 \(O(n^3)\)。

代码

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
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <vector>
int read(){
    register int x = 0;
    register char f = 1, ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = !f;
    for (; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ '0');
    return f ? x : -x;
}
#define N 305
#define P 1000000007
int n, m, a[N], b[N], fa[N], rt, inv[N], inva[N], sz[N], dp[N][N][N], tmp[N];
std :: vector<int> E[N];
int qpow(int a, int b){
    int s = 1;
    for (; b; b >>= 1, a = 1ll * a * a % P) if (b & 1) s = 1ll * s * a % P;
    return s;
}
void add(int &x, int y){
    (x += y) >= P ? x -= P : 0;
}
void dfs(int u){
    sz[u] = 1;
    for (register int i = 0; i < b[u]; ++i) dp[u][i][1] = 1ll * (a[i + 1] - a[i]) * inva[b[u]] % P;
    for (register int i = 0; i < E[u].size(); ++i){
        int v = E[u][i], sum = 0;
        dfs(v);
        for (register int j = b[v] - 1; j >= b[u]; --j)
            for (register int k = 1; k <= sz[v]; ++k)
                add(sum, dp[v][j][k]);
        for (register int j = b[u] - 1; ~j; --j){
            for (register int k = 1; k <= sz[u] + sz[v]; ++k) tmp[k] = 0;
            for (register int k = 1; k <= sz[u]; ++k)
                for (register int l = 1; l <= sz[v]; ++l)
                    add(tmp[k + l], 1ll * dp[u][j][k] * dp[v][j][l] % P);
            for (register int k = 1; k <= sz[u] + sz[v]; ++k)
                dp[u][j][k] = (1ll * dp[u][j][k] * sum + tmp[k]) % P;
            for (register int k = 1; k <= sz[v]; ++k) add(sum, dp[v][j][k]);
        }
        sz[u] += sz[v];
    }
    for (register int j = 0; j < b[u]; ++j)
        for (register int k = 1; k <= sz[u]; ++k)
            dp[u][j][k] = 1ll * dp[u][j][k] * inv[k] % P;
}
int main(){
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);
    n = read();
    for (register int i = 1; i <= n; ++i){
        a[i] = b[i] = read(), fa[i] = read();
        if (fa[i]) E[fa[i]].push_back(i); else rt = i;
    }
    std :: sort(a + 1, a + 1 + n);
    m = std :: unique(a + 1, a + 1 + n) - a - 1;
    for (register int i = 1; i <= n; ++i)
        b[i] = std :: lower_bound(a + 1, a + 1 + m, b[i]) - a;
    for (register int i = 1; i <= n; ++i) inv[i] = qpow(i, P - 2);
    for (register int i = 1; i <= m; ++i) inva[i] = qpow(a[i], P - 2);
    dfs(rt);
    int ans = 0;
    for (register int i = 0; i < b[rt]; ++i)
        for (register int j = 1; j <= n; ++j)
            add(ans, dp[rt][i][j]);
    printf("%d", ans);
}

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://autumnkite.github.io/vc190705A-sol/

更新于：2021年8月23日

DP

概率

树形DP

评论