QAQ我是第41个。。我以为这是概率dp入门题，只是n这么大让蒟蒻有点蒙啊。。最后还是runtime error9次才AC

#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#define maxn 1005
using namespace std;

int n,m,c;
float f[maxn][105];

int main(){
    while(scanf("%d",&c)!=EOF){
        if(c==0)return 0;
        scanf("%d%d",&n,&m);
        memset(f,0.0,sizeof(f));
        if(m>c||((n&1)!=(m&1))){printf("0.000\n");continue;}
        if(n>1000){if(n&1)n=1001;else n=1000;}
        f[0][0]=1.0;
        float p=1.0/c;
        for(int i=1;i<=n;i++){
            for(int j=0;j<=i&&j<=c;j++){
                if(j>0)f[i][j]+=f[i-1][j-1]*(c-j+1)*p;
                if(j+1<=i-1&&j+1<=c)
                    f[i][j]+=f[i-1][j+1]*(j+1)*p;
            }
        }
        printf("%.3f\n",f[n][m]);       
    }

}

不要问我为啥n大于1000可以那么做，我都是看大佬的题解才这么改的。。毕竟我只是来入门的

if(n>1000){ if(n%2==1) n=1001; else n=1000; }
Dp[i][j]:=取到第i个巧克力的时候剩下j个巧克力的概率。。
理清楚，i-j个巧克力全都成双成对了，如果不存在这个情况自然而然这个dp[i][j]==0.....
初始化dp[0][0]=1;
###Block code
for(int i=1;i<=n;i++)
for(int j=0;j<=c&&j<=i;j++) //这里要注意j的范围 是j<=c而不是j<=m
{
Dp[i][j]+=dp[i-1][j-1]*(c-j+1)*p; //if(j>0) //当前第i个落单了。
Dp[i][j]+=dp[i-1][j+1]*(j+1)*p； //j+1<=i+1&&j+1<=c //与前面落单的j+1任一个合成
}

测试数据 01：答案正确... 150ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：150ms

OTL,琢磨半天就一组数据...

其实不用生成函数,因为当n足够大的时候所出的解趋向稳定,

又只保留三位,所以当n>1001的时候 n为奇则赋值为1001 为偶则赋值为1000.

这样纵使maxn=1000000,也可轻松压缩到1001...

边界：f := f + f;

方程：f := f + f*j/c;

//第i次取剩余j种中有的颜色吃掉

f := f + f*(c-j)/c;

//不吃这一个

至于想构造母函数,黑书P259有详细讲解,在此不赘述...

ps : 其实不要看通过率 通过人数很低就吓到了...

很简单的...

Oh~第25人~5%...

最好用母函数，如果DP也行

母函数解法：

分子是(1+X）^c中X^m的系数

分母是(1+X）^c中与n同奇偶且指数小于C的系数的和

如样例

分子 X^2系数是10

分母 X^0 X^2 X^4(指数

ACM/ICPC Regional Contest Beijing 2002 Problem F
黑书P259 【例3】

double f(int n)
{
    if(!n)return 1;
    if(n==1)return 1;
    return n*f(n-1);
}
int main(void)
{
    int c,m,n;
    double sum=0,z;
    scanf("%d%d%d",&c,&m,&n);
    if(m%2){
        if(n%2==0||n>c){
            printf("%d",0);
            return 0;
        }
        for(int i=1;i<=c;i+=2){
            sum+=(f(c)/(f(i)*f(c-i)));
            if(i==n)
            z=(f(c)/(f(i)*f(c-i)));
        }
    }
    else{
        if(n%2==1||n>c){
            printf("%d",0);
            return 0;
        }
        for(int i=0;i<=c;i+=2){
            sum+=(f(c)/(f(i)*f(c-i)));
            if(i==n)
            z=(f(c)/(f(i)*f(c-i)));
        }   
    }
    printf("%.3f",z/sum);
    return 0;
    
}```
怎么不对啊？

ge

好像C++要把DOUBLE 类型全换成FLOAT
然后N太大就
if(n>1000){
if(n%2==1) n=1001;
else n=1000;
}
就可以DP了。谢谢几年前的人的留言

无限膜拜mike_nzk超级神牛!!!!!

母函数就是强悍!!!!!!!!

刚开始想用纯DP........但是后来不得不把母函数放进去.....

但是......N

这道题深深的把我囧到了。。。。。。。。。。。还是dp比较好。。

引用nzk神牛的题解：

此题其实是一个很简单的DP（或者可以说是递推）。

假设f表示取了i个巧克力，剩下j个巧克力的可能性，那么可以得到：

f=(c-j+1)/c*f{j>0，表示第i个巧克力落单，无法被吃掉}+(j+1)/c*f{j=1000时，“母函数法”求出的值已经足以近似正解了。

另外，此题还有一些特殊情况可以直接判断无解。

因此，此题算法流程如下：

读入c,n,m;

如果m>c或n

其实此题还是比较简单的

几种情况直接输出0.000

1、N>M

2、M>C

3、（N+M）and 1=1（即同奇偶）

当N=1000时

用母函数算

(上述情况mike_nzk大牛的题解里已给出，

开始一直在想N取多少时dp比较好= =|)

那个系数就是一个杨辉三角

因为精度要求比较弱，

所以直接用Extended存储在C*C的数组里就可以了

7次AC！0ms！

由于没人写题解，所以我就写一个（其实此方法非正解）：

n>=5000 时

计算 2*C(c,m)/2^c 即可。

注意：c=0 时结束！

白交10次！

Cheat...

交了51次才AC的某超级菜鸟飘过。

精度要求不高,可以考虑DP

通过出题人的指示

虽然没看懂怎么用MHS

但是知道了答案跟N的奇偶性有关系

所以N太大的时候可以转化成较小的同奇偶的N

我取在了20C左右

ai.....

数据有问题吧,我自己手算对的啊

100 1000000 1000000

这样的数据X^m系数算几？