Solution -「ACM-ICPC BJ 2002」「POJ 1322」Chocolate (mathcal{Description}) (mathcal{Solution})
Link.
(c) 种口味的的巧克力，每种个数无限。每次取出一个，取 (n) 次，求恰有 (m) 个口味出现奇数次的概率。
(mathcal{Solution})
由于比较板（且要补的题太多），所以会简略一点。
首先，(n,m) 不同奇偶；(m) 大于 (c) 或 (n) 无解，特判掉。考虑到“取出”有序，引入 ( ext{EGF})。显然题目要求：
[[x^n]inom{c}{m}left(frac{e^x+e^{-x}}2
ight)^{c-m}left(frac{e^x-e^{-x}}2
ight)^m
]
记后面这个式子为 (G(x))，推导：
[egin{aligned}G(x)&=inom{c}{m}2^{-c}(e^x+e^{-x})^{c-m}(e^x-e^{-x})^m\&=inom{c}{m}2^{-c}sum_{i=0}^{c-m}sum_{j=0}^m(-1)^jinom{c-m}{i}inom{m}{j}e^{(c-2i-2j)x}\&=inom{c}{m}2^{-c}sum_{i=0}^{c-m}sum_{j=0}^m(-1)^jinom{c-m}{i}inom{m}{j}sum_{k=0}^{+infty}frac{(c-2i-2j)^k}{k!}end{aligned}
]
代入 (k=n)，(mathcal O(n^2)) 求解，注意精度。
(mathcal{Code})
#include <cstdio>
const int MAXC = 100;
int c, n, m;
double comb[MAXC + 5][MAXC + 5];
inline void init () {
comb[0][0] = 1;
for ( int i = 1; i <= MAXC; ++ i ) {
comb[i][0] = 1;
for ( int j = 1; j <= i; ++ j ) {
comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
}
}
}
inline double qkpow ( double a, int b ) {
double ret = 1;
for ( ; b; a *= a, b >>= 1 ) ret *= b & 1 ? a : 1.0;
return ret;
}
int main () {
init ();
while ( ~ scanf ( "%d", &c ) && c ) {
scanf ( "%d %d", &n, &m );
if ( ( n & 1 ) ^ ( m & 1 ) || m > c || m > n ) { puts ( "0.000" ); continue; }
double ans = 0;
for ( int i = 0; i <= c - m; ++ i ) {
for ( int j = 0; j <= m; ++ j ) {
ans += ( j & 1 ? -1 : 1 ) * comb[c - m][i]
* comb[m][j] * qkpow ( ( c - 2.0 * i - 2.0 * j ) / c, n );
}
}
ans = ans * comb[c][m] / qkpow ( 2, c );
printf ( "%.3f
", ans );
}
return 0;
}