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 \leq 15, m, a_{i} \leq 100$

Solution

我们考虑枚举哪些 $a_{i}$ 最终会变成 $0$ ，我们令这些 $a_{i}$ 为集合 $S$ ，令 $c n t_{S}$ 表示 $| S |$ 的大小， $s u m_{S}$ 表示 $S$ 中 $a_{i}$ 的和

我们考虑用 $D P$ 计算所有序列的概率和，令 $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 - s u m_{S}}{a_{k} - 1}) \frac{1}{n - c n t_{S}} f_{i, S}$ ，如果填一个 $x$ ，那么贡献为 $\frac{1}{n - c n t_{S}} f_{i, S}$

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

时间复杂度 $O (2^{n} m^{2})$

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