大本赢彩票开户

码迷,xscp18.com
大本赢彩票开户 > 其他好文 > 详细

【CF457D】Bingo!(数学 期望)

时间:2019-11-01 00:08:14      阅读:19      评论:0      收藏:0      [点我收藏+]

标签:can   name   algo   span   display   表示   codeforce   不同的   多次   

大意

给定\(N,M,K\),表示有一个\(N*N\)的空矩阵,\(M\)个不同的数。
随机地把\(M\)个数中的\(N^2\)个数丢进这个空矩阵中(\(M\ge N^2\)
再从\(M\)个数中随机选\(K\)个不同的数,在矩阵上将这\(K\)个数标记出来(如果有)。
\(T\)的值为完全被标记的整行与整列个数。
\(2^T\)的期望值与\(1e99\)的较小值。

思路

首先,对于\(2^T\)这种奇怪的东西,我们可以将其理解为该种情况的所有子集个数。
即有些情况可能会被多次计算也是合法的,所以不用容斥。
则答案就是所有的\(T\)值出现个数的期望值。

然后有一个比较显然的想法:不妨枚举一下\(R,C\),表示至少\(R\)整行,\(C\)整列被标记完。
则此时有一个\(C(N,R)\times C(N,C)\)表示在该情况下的\(T\)值总个数。
而这种方案的出现概率\(P[R][C]\)的值就为出现该情况数除以总情况数。
我们不妨设\(Z=(R+C)\times N-R\times C\),即这\(Z\)个数都会在所选的\(K\)个数中。
则有:
\[P[R][C]=\frac{C(M,K)\cdot A(K,Z)\cdot A(M-Z,N^2-Z)}{C(M,K)\cdot A(M,N^2)}\]
将该式子化简后得:
\[P[R][C]=\frac{C(M-Z,K-Z)}{C(M,K)}\]

即该情况对答案的贡献就为\(C(N,R)\times C(N,C)\times \frac{C(M-Z,K-Z)}{C(M,K)}\)

小注:
对于\(P[R][C]\)的理解:

  • 对于第一个式子的理解:
    分子:枚举了\(K\)的选择,\(Z\)的上色选择,剩下的\(N^2-Z\)的上色选择。
    分母:考虑了每一种矩阵上色情况以及每一种\(K\)的选择的总方案数。
  • 对于第二个式子的理解:发现预涂色对答案统计无影响
    分子:\(Z\)个数的位置以及颜色已经固定,则这\(Z\)个数一定在\(K\)个数中,剩下的\(K-Z\)个乱选就行了。
    分母:矩阵的颜色已经上好,则总方案数只有\(C(M,K)\)

对于答案的保存方式:
使用long double来存储一个数的log()值,
则乘法变加法,除法变减法,最后再统一出解。

代码

#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
#define LD long double
const int MAXN=100005;
int N,M,K;
LD f[MAXN],Ans;
LD C(int x,int y){
    return f[x]-f[y]-f[x-y];
}
int main(){
    scanf("%d%d%d",&N,&M,&K);
    for(int i=1;i<=1e5;i++)
        f[i]=f[i-1]+log(1.0*i);
    for(int i=0;i<=N;i++)
        for(int j=0;j<=N;j++){
            int z=N*(i+j)-i*j;
            if(z>K)continue;
            LD tmp=C(N,i)+C(N,j)+C(M-z,K-z)-C(M,K);
            Ans=min((LD)(1e99),Ans+exp(tmp));
        }
    printf("%.10f\n",(double)Ans);
}

大本赢彩票开户【CF457D】Bingo!(数学 期望)

标签:can   name   algo   span   display   表示   codeforce   不同的   多次   

原文地址:https://www。cnblogs。com/ftotl/p/11774330。html

(0)
(0)
   
举报
评论 一句话评论(0
登录后才能评论!
           
© 2014 xscp18.com 版权所有 京ICP备13008772号-2
迷上了代码!
易富彩娱乐开户 新橙彩票开户 宏发彩票开户 易权彩票开户 皮皮彩开户 兴利彩票开户 众享彩票开户 豪客彩开户 35彩票开户 兴盛彩票开户