【题解】Chocolate [Uva1305] [Poj1322]

传送门：\(\text{Chocolate [Uva1305]}\) \(\text{[Poj1322]}\)

【题目描述】

有 \(c\) \((c\leqslant 100)\) 种颜色的小球若干，每次从中任取一个放在桌上，若桌上有与它颜色相同的其他小球，则把两个都丢掉。求取 \(n\) \((n\leqslant 10^6)\) 个小球，桌子上恰好剩下 \(m\) \((m\leqslant 10^6)\) 个的概率。

【分析】

显然可以写个概率 \(\text{DP}\)，加了玄学剪枝后复杂度 \(O(1000\times c)\)，也可以用生成函数做。

【Step 1】

将求概率转换为求：取球的合法排列数 \(g_{n}\) 。总情况数有 \(c^{n}\) 种，最终答案为 \(\frac{g_{n}}{c^{n}}\) 。

【Step 2】

考虑用生成函数求解 \(g(n)\) 。由于本题需要计算的是排列方案而非组合，如果用 \(\text{OGF}\) 的话，卷起来是无意义的，所以要用 \(\text{EGF}\) 定义。

易知留下来的 \(m\) 种颜色都分别被取了奇数次，未留下的 \(c-m\) 种颜色都分别被取了偶数次。

设指数型生成函数 \(F_1(x)=\sum_{n\geqslant 0}f_n\frac{x^n}{n!}\)，其表示的数列通项公式为 \(f_n=[n\mod 2=1]\)，意义为：只有一种颜色时，\(n\) 个小球所能构成的排列中所有颜色都出现了奇数次的合法排列数。

则有 \(m\) 种颜色时，所有颜色都出现了奇数次的合法排列数 \(\text{EGF}\) 为 \(F_1^m(x)\) 。

同理，设偶数次的生成函数 \(F_0(x)\)，则有 \(c-m\) 种颜色时为 \(F_0^{c-m}(x)\) 。

由于不知道最终留下的颜色是哪些，所以要乘个 \(C_{c}^{m}\)，故 \(g_{n}\) 序列的 \(\text{EGF}\) 为：\(G(x)=C_{c}^{m}F_1^{m}(x)F_0^{c-m}(x)\) 。

【Step 3】

首先将 \(F_0(x),F_1(x)\) 化为收敛形式：

\[F_0(x)=\sum_{n\geqslant 0}[n\mod 2=0]\frac{x^{n}}{n!}=\sum_{n\geqslant 0}\frac{x^{2n}}{(2n)!}=\frac{e^{x}+e^{-x}}{2} \]

\[F_1(x)=\sum_{n\geqslant 0}[n\mod 2=1]\frac{x^{n}}{n!}=\sum_{n\geqslant 0}\frac{x^{2n+1}}{(2n+1)!}=\frac{e^{x}-e^{-x}}{2} \]

二项式定理展开：

\[\begin{aligned} G(x)&=C_{c}^{m}(\frac{e^{x}-e^{-x}}{2})^{m}(\frac{e^{x}+e^{-x}}{2})^{c-m}\\ &=\frac{C_{c}^{m}}{2^c}\left(\sum_{i=0}^{m}(-1)^{i}C_{m}^{i}e^{(m-2i)x}\right)\left(\sum_{j=0}^{c-m}C_{c-m}^{j}e^{(c-m-2j)x}\right)\\ &=\frac{C_{c}^{m}}{2^c}\sum_{i=0}^{m}\sum_{j=0}^{c-m}(-1)^{i}C_{m}^{i}C_{c-m}^{j}e^{(c-2i-2j)x}\\ &=\frac{C_{c}^{m}}{2^c}\sum_{i=0}^{m} \sum_{j=0}^{c-m}(-1)^{i}C_{m}^{i}C_{c-m}^{j}\sum_{n\geqslant 0} \frac{x^n}{n!}(c-2i-2j)^{n}\\ &=\sum_{n\geqslant 0}\left(\frac{C_{c}^{m}}{2^c}\sum_{i=0}^{m} \sum_{j=0}^{c-m}(-1)^{i}C_{m}^{i}C_{c-m}^{j}(c-2i-2j)^{n}\right)\frac{x^n}{n!} \end{aligned} \]

因此合法排列数为 \(g(n)=\frac{C_{c}^{m}}{2^c}\sum_{i=0}^{m} \sum_{j=0}^{c-m}(-1)^{i}C_{m}^{i}C_{c-m}^{j}(c-2i-2j)^{n}\)

【Step 4】

算之前先特判一下无解的情况：\(m>n\) 或 \(m>c\) 。
由于有 \(n-m\) 个球是被成对取走了的，所以当 \(c-m\) 不为偶数时答案也为 \(0\) 。

另外，这题极其恶心地没有给取模，直接算 \(c^{n}\) 会炸上天，必须要丢到这里面去：\((c-2i-2j)^{n}\) 。

时间复杂度：\(O(c^2\log n)\) 。

【Code】

（这题精度极其迷惑，交 \(\text{Poj}\) 必须要用%f输出。\(\text{Uva}\) 上生成函数做法过不了，如果想 \(\text{AC}\) 就写个 \(\text{DP}\) 吧...）

#include<algorithm>
#include<cstring>
#include<cstdio>
#define LD double
#define LL long long
#define Re register int
using namespace std;
const int N=1e6+3,M=103;
int c,n,m;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline LD mi(LD x,Re k){
    LD s=1;
    while(k){
        if(k&1)s*=x;
        x*=x,k>>=1;
    }
    return s;
}
LD C[M][M];
inline void get_C(Re N){
    for(Re i=0;i<=N;++i)C[i][i]=C[0][i]=1;
    for(Re i=1;i<=N;++i)
        for(Re j=1;j<i;++j)
            C[j][i]=C[j-1][i-1]+C[j][i-1];
}
int main(){
//    freopen("123.txt","r",stdin);
    get_C(M-3);
    while(~scanf("%d",&c)&&c){
        in(n),in(m);
        if(m>c||m>n||(n-m)&1){puts("0.000");continue;}
        LD ans=0;
        for(Re i=0;i<=m;++i)
            for(Re j=0;j<=c-m;++j)
                ans+=((i&1)?-1:1)*C[i][m]*C[j][c-m]*mi((LD)(c-(i<<1)-(j<<1))/c,n);
        ans*=C[m][c];
        for(Re i=1;i<=c;++i)ans/=2.0;
        printf("%.3f\n",ans);//交Poj时必须用%f输出
    }
}