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

题目描述

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;
}