题意:
给一个X * Y * Z 的立方体, 每个单位立方体内都有一盏灯, 初始状态是灭的, 你每次操作如下:
1)选择一个点(x1, y1, z1)
再选择一个点(x2, y2, z2)
将这两个点所形成的立方体内所有的灯全部转换状态(灭的变亮的, 亮的变灭的)
问, K次操作后, 亮着的灯的期望数目。
思路:
三维坐标系, 每个维度都是相互独立的, 所以可以分开计算再相乘。
考虑x轴, 对于每个点, 被选中的概率是多少:假设这个点左边有a个点,右边有b个点,
那么这个点不被选中的概率是p = 1.0 - ((x - 1) * (x - 1) - (a * a + b * b)) / x * x。
则,这个点在K次操作后被点亮的期望为:E = sigma C(k, i) * p * (1 - p) ^ (k - i),i为奇数, 因为i为偶数时灯是灭的。
这是二项展开式(p + (1 - p)) ^ k 的所有奇数项。
因此, E = ((p + (1 - p)) ^ k - (-p + (1 - p)) ^ k) / 2, 蓝色部分将所有的奇数项变成了负数, 偶数项不变, 相减后则成了两倍的奇数项之和。
代码:
1 #include <cmath>
2 #include <cstdio>
3 #include <cstring>
4 #include <cstdlib>
5 #include <ctime>
6 #include <set>
7 #include <map>
8 #include <list>
9 #include <queue>
10 #include <string>
11 #include <vector>
12 #include <fstream>
13 #include <iterator>
14 #include <iostream>
15 #include <algorithm>
16 using namespace std;
17 #define LL long long
18 #define INF 0x3f3f3f3f
19 #define MOD 1000000007
20 #define eps 1e-6
21 #define MAXN 1000000
22 #define dd cout<<"debug"<<endl
23 #define p(x) cout<<x<<endl
24 int x, y, z, k;
25 double qpow(double x, int k)
26 {
27 double res = 1.0;
28 while(k)
29 {
30 if(k & 1) res = res * x;
31 x = x * x;
32 k >>= 1;
33 }
34 return res;
35 }
36 double get_p(int x, int n)
37 {
38 return 1.0 - ((x - 1) * (x - 1) * 1.0 + (n - x) * (n - x) * 1.0) * 1.0 / (n * n);
39 }
40
41 int main()
42 {
43 int T;
44 int kcase = 0;
45 scanf("%d", &T);
46 while(T --)
47 {
48 double ans = 0.0;
49 scanf("%d %d %d %d", &x, &y, &z, &k);
50 for(int i = 1; i <= x; i ++)
51 for(int j = 1; j <= y; j ++)
52 for(int g = 1; g <= z; g ++)
53 {
54 double p = get_p(i, x) * get_p(j, y) * get_p(g, z);
55 ans += (1.0 - qpow(1 - 2.0 * p, k)) / 2.0;
56 }
57 printf("Case %d: %.7lf\n", ++kcase, ans);
58 }
59 return 0;
60 }