Description
Link.
包里有无穷多个巧克力，巧克力有 (c) 种颜色，每次从包里拿出不同颜色巧克力的概率都是相等的，桌面的巧克力不允许颜色相同，若某次拿出的巧克力与桌上的巧克力颜色相同了，则将两颗巧克力都吃掉。计算进行 (n) 次拿巧克力的操作后，桌上有 (m) 颗巧克力的概率。
Solution
本质是给在 (c) 种颜色选 (m) 种颜色每种选奇数次，剩下 (c-m) 中每种选偶数次。
构造那 (c-m) 种和 (m) 种的 egf：
[egin{aligned}
G_{1}(x)&=sum_{i=0}^{infty}frac{x^{2i}}{(2i)!} \
G_{2}(x)&=sum_{i=0}^{infty}frac{x^{2i+1}}{(2i+1)!}
end{aligned}
]
换成 (e) 的形式:
[egin{aligned}
G_{1}(x)&=frac{e^{x}-e^{-x}}{2} \
G_{2}(x)&=frac{e^{x}+e^{-x}}{2}
end{aligned}
]
那么方案数的 ogf 为：
[G(x)=left(frac{e^{x}-e^{-x}}{2}
ight)^{m} imesleft(frac{e^{x}+e^{-x}}{2}
ight)^{c-m}
]
那么答案即为：
[frac{[G_{n}] imes n! imesinom{c}{m}}{c^{n}}
]
考虑怎么求出 ([G_{n}])。我们把 (G) 看成关于 (e^{x})，然后二项式展开后卷积：
[egin{aligned}
G(x)&=left(frac{e^{x}-e^{-x}}{2}
ight)^{m} imesleft(frac{e^{x}+e^{-x}}{2}
ight)^{c-m} \
&=2^{-c} imesleft(sum_{i=0}^{m}inom{m}{i}(-1)^{i}e^{x(m-2i)}
ight) imesleft(sum_{i=0}^{c-m}inom{c-m}{i}e^{(2i+m-c)x}
ight) \
&=2^{-c} imesleft(sum_{i=0}^{m}sum_{j=0}^{c-m}(-1)^{i}inom{m}{i}inom{c-m}{j}e^{x(2m-2i+2j-c)}
ight) \
&=2^{-c} imesleft(sum_{i=0}^{m}sum_{j=0}^{c-m}(-1)^{i}inom{m}{i}inom{c-m}{j}left(sum_{k=0}^{infty}frac{(x(2m-2i+2j-c))^{k}}{k!}
ight)
ight)
end{aligned}
]
这份代码是在 POJ 上过的，至于 UVa 这边不想管了。
#include<bits/stdc++.h>
using namespace std;
int comb[210][210],c,n,m;
double ans;
double qpow(double bas,int fur)
{
double res=1;
while(fur)
{
if(fur&1) res*=bas;
bas*=bas;
fur>>=1;
}
return res;
}
int main()
{
for(int i=0;i<=100;++i) comb[i][0]=comb[i][i]=1;
for(int i=2;i<=100;++i) for(int j=1;j<i;++j) comb[i][j]=comb[i-1][j]+comb[i-1][j-1];
while(~scanf("%d",&c)&&c)
{
ans=0;
scanf("%d %d",&n,&m);
if(m>c||m>n||(n-m)%2) puts("0.000");
else
{
for(int i=0,now=1;i<=m;++i,now*=-1) for(int j=0;j<=c-m;++j) ans+=now*comb[m][i]*comb[c-m][j]*qpow(double(2*m-2*i+2*j-c)/c,n);
ans*=comb[c][m]; ans/=qpow(2,c);
printf("%.3f
",ans);
}
}
return 0;
}