Gym 101174D Dinner Bet（概率DP）题解

时间：2025-03-21 17:33:07

题意：n个球，两个人每人选C个球作为目标，然后放回。每回合有放回的拿出D个球，如果有目标球，就实现了这个目标，直到至少一个人实现了所有目标游戏结束。问结束回合的期望。误差1e-3以内。

思路：概率DP，因为终止条件是目标数，那么A的目标数B的目标数是一定要有的，但是AB之间可能有交集，那么我就把他单独列出来，我们设dp[t][i][j][k]表示第t回合a有i个独有的没涂b有j个独有的没涂有k个共有的没涂。那么我们可以得到状态转移方程：

$\LARGE{dp[t][ii][jj][kk] = dp[t - 1][i][j][k] * \frac{C^{i - ii}_{i}  *  C^{j - jj}_{j}  *  C^{k - kk}_{k}  *  C^{d - (i - ii) - (j - jj) - (k - kk)}_{n - i - j - k}}{C_{n}^{d}}}$

代码：

#include<cmath>

#include<set>

#include<map>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include <iostream>

#include<algorithm>

#include<unordered_map>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int maxn = 1e3 + 10;

const int M = maxn * 30;

const ull seed = 131;

const int INF = 0x3f3f3f3f;

const int MOD = 1e4 + 7;

double dp[maxn][15][15][15];

//第t回合a有i个没涂b有j个没涂有k个共有的没涂

double C[65][65];   //Cn m

int n, d, c, sz, cmn;

set<int> a;

void init(){

    C[0][0] = C[1][0] = C[1][1] = 1;

    for(int i = 2; i < 60; i++){

        for(int j = 0; j <= i; j++){

            C[i][j] = j == 0? 1 : C[i - 1][j - 1] + C[i - 1][j];

        }

    }

}

double solve(int i, int j, int k, int ii, int jj, int kk){

    //printf("%f\n", C[i][i - ii] * C[j][j - jj] * C[k][k - kk] * C[n - i - j - k][d - (i - ii) - (j - jj) - (k - kk)] / C[n][d]);

    return C[i][i - ii] * C[j][j - jj] * C[k][k - kk] * C[n - i - j - k][d - (i - ii) - (j - jj) - (k - kk)] / C[n][d];

}

int main(){

    init();

    scanf("%d%d%d", &n, &d, &c);

    a.clear();

    cmn = 0;

    for(int i = 1; i <= c; i++){

        int x;

        scanf("%d", &x);

        a.insert(x);

    }

    for(int i = 1; i <= c; i++){

        int x;

        scanf("%d", &x);

        if(a.count(x)) cmn++;

    }

    for(int t = 0; t <= 1000; t++)

        for(int i = 0; i <= c - cmn; i++)

            for(int j = 0; j <= c - cmn; j++)

                for(int k = 0; k <= cmn; k++)

                    dp[t][i][j][k] = 0;

    dp[0][c - cmn][c - cmn][cmn] = 1;

    for(int t = 1; t <= 1000; t++){

        for(int i = 0; i <= c - cmn; i++){

            for(int j = 0; j <= c - cmn; j++){

                for(int k = 0; k <= cmn; k++){

                    for(int ii = 0; ii <= i; ii++){

                        for(int jj = 0; jj <= j; jj++){

                            for(int kk = 0; kk <= k; kk++){

                                if(i - ii + j - jj + k - kk > d) continue;

                                if(i + j + k > n) continue;

                                if(i + k == 0 || j + k == 0) continue;

                                dp[t][ii][jj][kk] += dp[t - 1][i][j][k] * solve(i, j, k, ii, jj, kk);

                            }

                        }

                    }

                }

            }

        }

    }

    double ans = 0;

    for(int t = 1; t <= 1000; t++){

        for(int i = 1; i <= c - cmn; i++)

            ans += dp[t][i][0][0] * t + dp[t][0][i][0] * t;

        ans += dp[t][0][0][0] * t;

    }

    printf("%.5lf\n", ans);

    return 0;

}

/*

30 5 10

2 3 5 7 11 13 17 19 23 29

20 18 16 14 12 10 8 6 4 2

*/

相关文章