传送门
生成函数好题。
题意简述：一个袋子里有ccc种不同颜色的球，现要操作nnn次，每次等概率地从袋中拿出一个球放在桌上，如果桌上有两个相同的球就立刻消去，问最后桌上剩下mmm个球的概率。
第一眼反应是概率dpdpdp，怼了一波式子之后发现要TTT果断弃掉。
我们考虑推答案的式子吧。
由题可知，ccc种球有mmm个出现奇数次，c−mc-mc−m个出现偶数次。
于是我们对每一种颜色构造生成函数（指数型）
算出来f(x)=Ccm(ex−e−x2)m(ex+e−x2)c−mncf(x)=\frac{C_c^m(\frac{e^x-e^{-x}}2)^m(\frac{e^x+e^{-x}}2)^{c-m}}{n^c}f(x)=ncCcm(2ex−e−x)m(2ex+e−x)c−m
然后把分子后面两坨二项式展开。
推出来:
f(x)f(x)f(x)的系数=Ccm∑i=0m∑j=0c−m(−1)m−iCmiCc−mje2(i+j)−cnc=Ccm∑i=0m∑j=0c−m(−1)m−iCmiCc−mj(kc)nnc=\frac{C_c^m\sum_{i=0}^m\sum_{j=0}^{c-m}(-1)^{m-i}C_m^iC_{c-m}^je^{2(i+j)-c}}{n^c}=\frac{C_c^m\sum_{i=0}^m\sum_{j=0}^{c-m}(-1)^{m-i}C_m^iC_{c-m}^j(\frac kc)^n}{n^c}=ncCcm∑i=0m∑j=0c−m(−1)m−iCmiCc−mje2(i+j)−c=ncCcm∑i=0m∑j=0c−m(−1)m−iCmiCc−mj(ck)n
注意pojpojpoj这个OJOJOJ上面不能用lflflf（怒
代码：
#include<iostream>
#include<cstdio>
#define ri register int
using namespace std;
const int K=105;
double C[K][K];
int n,m,c;
inline void init(){
C[0][0]=1;
for(ri i=1;i<=100;++i)C[i][i]=C[i][0]=1,C[i][1]=i;
for(ri i=2;i<=100;++i)for(ri j=2;j<i;++j)C[i][j]=C[i-1][j]+C[i-1][j-1];
}
inline double ksm(double a,int p){double ret=1.0;for(;p;p>>=1,a=a*a)if(p&1)ret=ret*a;return ret;}
int main(){
init();
while(scanf("%d",&c),c){
scanf("%d%d",&n,&m);
if(((n-m)&1)||m>c||m>n){puts("0.000");continue;}
double sum=0.0;
for(ri i=0;i<=m;++i){
for(ri j=0;j<=c-m;++j){
double tmp=C[m][i]*C[c-m][j]*ksm((double)(2*(i+j)-c)/(double)c,n);
if((m-i)&1)sum-=tmp;
else sum+=tmp;
}
}
printf("%.3f\n",sum/ksm(2.0,c)*C[c][m]);
}
return 0;
}