2016-2017 ACM-ICPC Southwestern European Regional Programming Contest (SWERC 2016) D.Dinner Bet 概率DP+排列组合

题目链接：点这里

题意：

　　1~N标号的球

　　现在A有C个，B有C个

　　每次可以随机得到D个不同的球(1~N);问你A或B中的C个球都出现一次的期望次数

题解：

　　dp[i][j][k]表示随机出现了i个仅仅属于A的球的个数，仅仅属于B的球的个数，同时属于A,B的球的个数

#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define ls i<<1
#define rs ls | 1
#define mid ((ll+rr)>>1)
#define pii pair<int,int>
#define MP make_pair
typedef long long LL;
const long long INF = 1e18+1LL;
const double Pi = acos(-1.0);
const int N = 1e5+10, M = 1e3+20, mod = 1e9+7, inf = 2e9;


LL Con[51][51];
double dp[12][12][12];
int vis[12][12][12],cnt[10],n,d,C,id[100];
double dfs(int i,int j,int k) {
    if(vis[i][j][k]) return dp[i][j][k];
    double& ret = dp[i][j][k];
    vis[i][j][k] = 1;
    if(i + k >= C || j + k >= C) return ret = 0;
    double tmp = 1;
    double xx;
    for(int a = 0; a + i <= cnt[1]; ++a) {
        for(int b = 0; b + j <= cnt[2]; ++b) {
            for(int c = 0; c + k <= cnt[3]; ++c) {
                if(a+b+c > d) continue;
                double p = 1.0*Con[cnt[1]-i][a] *
                Con[cnt[2]-j][b] * Con[cnt[3]-k][c] *
                Con[n-cnt[1]-cnt[2]-cnt[3]+i+j+k][d-a-b-c]/Con[n][d]*1.0;
                if(a+b+c==0) {
                    xx = p;
                }
                else
                {
                    tmp += p*dfs(i+a,j+b,k+c);
                }
            }
        }
    }
    ret = tmp/(1-xx);
    return ret;
}
int main()
{
    for(int i = 0; i <= 50; ++i) {
        Con[i][0] = 1,Con[i][i] = 1;
        for(int j = 1; j < i; ++j)
            Con[i][j] = Con[i-1][j] + Con[i-1][j-1];
    }
    scanf("%d%d%d",&n,&d,&C);
    for(int i = 0; i < 2; ++i) {
        for(int j = 1; j <= C; ++j) {
            int x;
            scanf("%d",&x);
            id[x] |= (1<<i);
        }
    }
    for(int i = 1; i <= n; ++i) if(id[i]) cnt[id[i]]++;
    printf("%.12f
",dfs(0,0,0));
    return 0;
}

/*
2 1 1
1 2


30 5 10
2 3 5 7 11 13 17 19 23 29
20 18 16 14 12 10 8 6 4 2
*/

2016-2017 ACM-ICPC Southwestern European Regional Programming Contest (SWERC 2016) D.Dinner Bet 概率DP+排列组合

相关推荐