CF457D Bingo! 概率，期望复习

好久没做概率题了

基本上自己想不出来每次都得看题解学

这道题基本上没人写 题解 ，我来占个沙发

\(Firstly\),思路

期望
\[ans=\displaystyle\sum^{n}_{r=0}\sum^{n}_{c=0}C_{n}^{r}*C_{n}^{c}*p_{r,c}\]

重点算\(p_{r,c}\)

从\(m\)中选出\(k\)个数分布在选中的\(r\)行\(c\)列

\(r\)行\(c\)列 共有 \(num=(r+c)*n-r*c\)个

\(num\)个数已经选出来且分布在选中的\(r\)行\(c\)列

剩下\(C_{m-num}^{k-num}\)选数方式

\[p_{r,c}=\frac{C_{m-num}^{k-num}}{C_{m}^{k}}\]

关键是此题数据很大 又没有说取模

那么可以想到用指数进行运算

应该知道

\[log(n)=log_{e}n\]

\[exp(x)=e^x\]

\(Attention\)

用\(long double\)

输出 转成\(double\) 再用\(lf\) 输出

用 \(Lf\)输出\(long double\)本地可过 \(CF\)上会错 （雾）

\(vjudge\) 上语言选 GNU \(G++11 5.1.0\)

\(Code\)

#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
#define reg register int
#define isdigit(x) ('0' <= (x)&&(x) <= '9')
template<typename T>
inline T Read(T Type)
{
    T x = 0,f = 1;
    char a = getchar();
    while(!isdigit(a)) {if(a == '-') f = -1;a = getchar();}
    while(isdigit(a)) {x = (x << 1) + (x << 3) + (a ^ '0');a = getchar();}
    return x * f;
}
typedef long double lb;
const int MAXN = 100010;
lb f[MAXN],ans;
inline lb C(int n,int m)
{
    return f[n] - f[m] - f[n - m];
}
int main()
{
    int n = Read(1),m = Read(1),k = Read(1);
    for(reg i = 1;i <= 1e5;i++) f[i] = f[i - 1] + log(1.0 * i);
    for(reg i = 0;i <= n;i++)
    {
        for(reg j = 0;j <= n;j++)
        {
            int num = (i + j) * n - i * j;
            if(num <= k)
            {
                lb p = C(n,i) + C(n,j) + C(m - num,k - num) - C(m,k);
                ans = min(ans + exp(p),(lb)1e99);
            }
        }
    }
    printf("%.10lf",(double)ans);
    return 0;
}

CF457D Bingo! 概率，期望复习

原文：https://www.cnblogs.com/resftlmuttmotw/p/11725936.html