DDOSvoid's Blog

2020 China Collegiate Programming Contest, Weihai Site E So Many Possibilities...

发表于 分类于
本文字数： 2.1k 阅读时长 ≈ 2 分钟

题目描述

https://codeforces.com/gym/102798/problem/E

简要题意：给定一个长度为 $n$ 的序列 $a_i$，每秒会随机选择一个大于 $0$ 的 $a_i$ 将其减 $1$，求 $m$ 秒后期望有多少个 $a_i=0$

$n\le 15,m,a_i\le 100$

Solution

我们考虑枚举哪些 $a_i$ 最终会变成 $0$，我们令这些 $a_i$ 为集合 $S$，令 $cnt_S$ 表示 $|S|$ 的大小，$sum_S$ 表示 $S$ 中 $a_i$ 的和

我们考虑用 $DP$ 计算所有序列的概率和，令 $f_{i,S}$ 表示现在过了 $i$ 秒，$S$ 中的 $a_k$ 都已经变成 $0$ 的概率和，注意我们记录后面某个 $a_k$ 会变成 $0$ 的状态，所以我们的序列中有一个特殊元素 $x$ 表示这个位置填的东西待定，那么我们 $f_{i,S}$ 的向后转移有两种选择，第一种是选择一个新的 $a_k$，它变成了 $0$，也就意味着第 $i+1$ 填 $k$，前 $i$ 秒中有 $a_k-1$ 个 $x$ 会变成 $k$，那么贡献为 $\binom{i-sum_{S}}{a_k-1}\frac{1}{n-cnt_{S}}f_{i,S}$，如果填一个 $x$，那么贡献为 $\frac{1}{n-cnt_S}f_{i,S}$

但是这个东西并不是答案，我们还需要将剩下的 $x$ 变成 $U-S$ 中的数字，显然每种序列都是不同的，所以我们需要在乘上一个 $g_{m-cnt_S,U-S}$ 表示在 $U-S$ 中选择 $m-cnt_S$ 个数字组成的序列个数

时间复杂度 $O(2^nm^2)$ 

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
#include <iostream>
#include <cmath>
#include <iomanip>
#define maxn 16
#define maxm 101
#define ll long long
using namespace std;

int n, m, a[maxn];

double C[maxm][maxm];
void init_C(int n) {
    for (int i = 0; i <= n; ++i) C[i][0] = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= i; ++j) C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
}

int cnt[1 << 15], sum[1 << 15];
    
double f[maxn][maxm];
double g[1 << 15][maxm];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m; init_C(m); 
    for (int i = 1; i <= n; ++i) cin >> a[i];

    int M = (1 << n) - 1;
    for (int S = 0; S <= M; ++S) 
        for (int i = 1; i <= n; ++i) 
            if (S >> i - 1 & 1) ++cnt[S], sum[S] += a[i];
    
    g[0][0] = 1; 
    for (int S = 0; S < M; ++S) 
        for (int k = 0; k <= m; ++k) {
            if (!g[S][k]) continue;
            g[S][k + 1] += g[S][k] / (n - cnt[S]);
            for (int i = 1; i <= n; ++i) {
                if (S >> i - 1 & 1) continue;
                if (k - sum[S] >= a[i] - 1)
                    g[S | 1 << i - 1][k + 1] += g[S][k] * C[k - sum[S]][a[i] - 1] / (n - cnt[S]);
            }
        }

    double ans = 0; 
    for (int S = 1; S <= M; ++S) {
        int t = 0; 
        for (int i = 0; i <= n; ++i)
            for (int j = 0; j <= m; ++j) f[i][j] = 0;
        f[0][0] = 1; 
        for (int i = 1; i <= n; ++i) {
            if (S >> i - 1 & 1) continue; ++t;
            for (int j = 0; j <= m; ++j)
                for (int k = 0; k <= min(a[i] - 1, j); ++k)
                    f[t][j] += f[t - 1][j - k] * C[j][k];
        }
        if (sum[S] > m) continue;
        ans += cnt[S] * g[S][m] * f[t][m - sum[S]];
    } cout << fixed << setprecision(7) << ans << "\n";
    return 0; 
}