§ Description

Link.

包里有无穷多个巧克力，巧克力有 $c$ 种颜色，每次从包里拿出不同颜色巧克力的概率都是相等的，桌面的巧克力不允许颜色相同，若某次拿出的巧克力与桌上的巧克力颜色相同了，则将两颗巧克力都吃掉。计算进行 $n$ 次拿巧克力的操作后，桌上有 $m$ 颗巧克力的概率。

§ Solution

本质是给在 $c$ 种颜色选 $m$ 种颜色每种选奇数次，剩下 $c-m$ 中每种选偶数次。

构造那 $c-m$ 种和 $m$ 种的 egf：

$$\begin{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$ 的形式:

$$\begin{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}\right)^{m}\times\left(\frac{e^{x}+e^{-x}}{2}\right)^{c-m}$$

那么答案即为：

$$\frac{[G_{n}]\times n!\times\binom{c}{m}}{c^{n}}$$

考虑怎么求出 $[G_{n}]$。我们把 $G$ 看成关于 $e^{x}$，然后二项式展开后卷积：

$$\begin{aligned} G(x)&=\left(\frac{e^{x}-e^{-x}}{2}\right)^{m}\times\left(\frac{e^{x}+e^{-x}}{2}\right)^{c-m} \\ &=2^{-c}\times\left(\sum_{i=0}^{m}\binom{m}{i}(-1)^{i}e^{x(m-2i)}\right)\times\left(\sum_{i=0}^{c-m}\binom{c-m}{i}e^{(2i+m-c)x}\right) \\ &=2^{-c}\times\left(\sum_{i=0}^{m}\sum_{j=0}^{c-m}(-1)^{i}\binom{m}{i}\binom{c-m}{j}e^{x(2m-2i+2j-c)}\right) \\ &=2^{-c}\times\left(\sum_{i=0}^{m}\sum_{j=0}^{c-m}(-1)^{i}\binom{m}{i}\binom{c-m}{j}\left(\sum_{k=0}^{\infty}\frac{(x(2m-2i+2j-c))^{k}}{k!}\right)\right) \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\n",ans);
		}
	}
	return 0;
}