首页 > 编程学习 > LightOJ-1284 Lights inside 3D Grid (概率计数)

LightOJ-1284 Lights inside 3D Grid (概率计数)

发布时间:2022/12/10 17:13:03

 

J - Lights inside 3D Grid

 LightOJ - 1284 

 

 

 

题解:概率计数。因为是求期望值,考虑每个点对答案的贡献:对每个点是亮着的概率求和就是所求期望。


那么每个点亮着的概率为多少呢?根据题意,对于点(x,y,z)只有当被选中的2个点(x1,y1,z1),(x2,y2,z2),
满足x1<=x<=x2且y1<=y<=y2且z1<=z<=z2时,该点的状态才会改变,因此对于每一维,

在区间内的概率=1-区间在该点的同一侧的概率
该点状态会改变的概率p=x维在区间内的概率*y维在区间内的概率*z维在区间内的概率


上述的只是状态改变一次的概率,题目中说会选择k次区间,根据异或原理,在这k次中,如果状态改变的次数为奇数次,那么该点最终是亮着的。
设f(x)为选择x次区间时,状态改变次数为奇数的概率,g(x)为状态改变次数为偶数的概率。
f(x)=(1-p)*f(x-1)+p*g(x-1)
g(x)=(1-p)*g(x-1)+p*f(x-1)
f(x)+g(x)=1
因此f(x)=(1-2p)*f(x-1)+p,两边同时除以(1-2p)^x,再化简成等比数列通项公式f(x)=0.5-0.5*(1-2p)^x

 

#include<cstdio>
#include<algorithm>
#include<string.h>
using namespace std;double P (int i, int x) {return 1.0 - 1.0 * ( (i - 1) * (i - 1) + (x - i) * (x - i)) / (x * x);
}
double pow (double a, int b) {double ret = 1;while (b) {if (b & 1) ret = ret * a;a = a * a;b >>= 1;}return ret;
}
int main() {int T, x, y, z, k;scanf ("%d", &T);for (int cas = 1; cas <= T; cas++) {scanf ("%d%d%d%d", &x, &y, &z, &k);double ans = 0;for (int i = 1; i <= x; i++) {for (int j = 1; j <= y; j++) {for (int s = 1; s <= z; s++) {double p = P (i, x) * P (j, y) * P (s, z);ans += 0.5 - 0.5 * pow (1 - 2 * p, k);}}}printf ("Case %d: %.7f\n", cas, ans);}return 0;
}

 

 

 

 

 


本文链接:https://www.ngui.cc/el/2314502.html
Copyright © 2010-2022 ngui.cc 版权所有 |关于我们| 联系方式| 豫B2-20100000