【POJ1322】Chocolate (生成函数)
Description
有
c
c
c种颜色的巧克力, 每种颜色有无限个. 现在每次取出一个巧克力, 其颜色等概率为
1
…
c
1\dots c
1…c中的一种.
问最终有
m
m
m种颜色的巧克力个数为奇数的概率.
n
≤
1
0
6
,
c
≤
100
n\le 10^6, c\le 100
n≤106,c≤100
Solution
睿智dp题。
设
f
i
,
j
f_{i,j}
fi,j表示当前取了
i
i
i个、有
j
j
j种颜色是奇数个的概率，直接dp即可，时间复杂度
O
(
n
c
)
O(nc)
O(nc)。
Code
/**************************************
* Au: Hany01
* Prob: poj1322
* Date: Nov, 18th, 2018
* Email: hany01@foxmail.com
**************************************/
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long LL;
typedef long double LD;
typedef pair<int, int> PII;
typedef vector<int> VI;
#define File(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)
#define Rep(i, j) for (register int i = 0, i##_end_ = j; i < i##_end_; ++ i)
#define For(i, j ,k) for (register int i = (j), i##_end_ = (k); i <= i##_end_; ++ i)
#define Fordown(i, j, k) for (register int i = (j), i##_end_ = (k); i >= i##_end_; -- i)
#define Set(a, b) memset(a, b, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define SZ(a) ((int)(a.size()))
#define ALL(a) a.begin(), a.end()
#define PB(a) push_back(a)
#define MP(a, b) make_pair(a, b)
#define X first
#define Y second
#define INF (0x3f3f3f3f)
#define INF1 (2139062143)
#define y1 WoXiHuanNiA
#ifdef hany01
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define debug(...)
#endif
template<typename T> inline bool chkmax(T &a, T b) { return a < b ? a = b, 1 : 0; }
template<typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; }
template<typename T> inline T read() {
register char c_; register T _, __;
for (_ = 0, __ = 1, c_ = getchar(); !isdigit(c_); c_ = getchar()) if (c_ == '-') __ = -1;
for ( ; isdigit(c_); c_ = getchar()) _ = (_ << 1) + (_ << 3) + (c_ ^ 48);
return _ * __;
}
//EOT
const int maxn = 105;
double fac[maxn];
inline void Init(int n) {
fac[0] = 1;
For(i, 1, n) fac[i] = fac[i - 1] * i;
}
inline double C(int n, int m) { return fac[n] / fac[m] / fac[n - m]; }
inline double fpm(double a, int b) {
register double ans = 1;
for ( ; b; b >>= 1, a *= a)
if (b & 1) ans *= a;
return ans;
}
double p[maxn], p_[maxn];
int main() {
#ifdef hany01
File("poj1322");
#endif
Init(100);
for (register int n, m, c; scanf("%d", &c) != EOF && c; ) {
n = read<int>(), m = read<int>();
if (m > c || m > n || ((n - m) & 1)) { puts("0.000"); continue; }
if (!n && !m) { puts("1.000"); continue; }
register double ans = 0;
Set(p, 0), Set(p_, 0);
For(i, 0, m) For(j, 0, c - m) {
int t = c - 2 * i - 2 * j;
if (t > 0) p[t] += C(m, i) * C(c - m, j) * ((i & 1) ? -1 : 1) / fpm(2, c);
else p_[-t] += C(m, i) * C(c - m, j) * ((i & 1) ? -1 : 1) / fpm(2, c);
}
For(k, 1, c) ans += fpm(1. * k / c, n) * (p[k] + ((n & 1) ? -1 : 1) * p_[k]) * C(c, m);
printf("%.3f\n", ans);
}
return 0;
}
True-Solution
这题的时间复杂度可以做到
O
(
c
log
)
O(c\log )
O(clog)。
首先要保证
m
≤
c
,
m
≤
n
m\le c, m\le n
m≤c,m≤n且
n
,
m
n,m
n,m同奇偶，否则概率为
0
0
0。
由于是排列，考虑指数型生成函数。
对于出现奇数次的巧克力，其指数型生成函数为：
f
1
(
x
)
=
e
x
−
e
−
x
2
f_1(x) = \frac{e^x - e^{-x}}{2}
f1(x)=2ex−e−x
出现偶数次的巧克力的生成函数为：
f
2
(
x
)
=
e
x
+
e
−
x
2
f_2(x) = \frac{e^x + e^{-x}}{2}
f2(x)=2ex+e−x
方案数即为
(
c
m
)
×
[
x
n
]
(
f
1
(
x
)
m
×
f
2
(
x
)
c
−
m
)
×
n
!
\binom{c}{m}\times [x^n](f_1(x)^m\times f_2(x)^{c-m})\times n!
(mc)×[xn](f1(x)m×f2(x)c−m)×n!。
(在
c
c
c中颜色中选择
m
m
m个取奇数次，
n
!
n!
n!是指数型生成函数需要乘的)
这时，时间复杂度的瓶颈在于
n
n
n，考虑怎么把
n
n
n去掉。
我们可以将
f
1
(
x
)
m
×
f
2
(
x
)
c
−
m
=
(
e
x
−
e
−
x
2
)
m
×
(
e
x
+
e
−
x
2
)
c
−
m
f_1(x)^m\times f_2(x)^{c-m}=\left(\frac{e^x-e^{-x}}{2}\right)^m\times \left(\frac{e^x+e^{-x}}{2}\right)^{c-m}
f1(x)m×f2(x)c−m=(2ex−e−x)m×(2ex+e−x)c−m看作一个关于
e
x
e^x
ex的多项式。
e
k
x
e^{kx}
ekx的系数对第
n
n
n项的贡献是
k
n
n
!
\frac{k^n}{n!}
n!kn，就可以把
n
!
n!
n!消掉了！
用FFT计算系数做到
c
log
c\log
clog（上面的代码是
O
(
c
2
)
O(c^2)
O(c2)计算的）。