UVA 11605 - Lights inside a 3d Grid

题目链接

题意：给定一个NxMxP的三维网格，每个格子上一盏灯，现在每次随机选择两点，把这两点构成立方体中间那一块开关灯状态转换，问K步之后网格中亮灯的期望

思路：概率问题，把x,y,z轴分开考虑，算出每一个点xi,yi,zi分别能被选到的情况数，然后根据乘法原理相乘起来除以总情况就能算出一点的概率，然后问题就是K次了，对于K次，每次开到的概率为P的情况下，总情况为∑k1Pi(1?P)k?ii为奇数，那么根据组合公式很容易化简为：
==》((1?p+p)k?(1?p?p)k)/2
==》(1?(1?2p)k)/2

然后对于每个点的期望加起来就是答案了

代码：

#include 
  
   
#include 
   
     #include 
    
      int t, n, m, p, K; double cal(double P) { return (1 - pow(1 - 2 * P, K)) / 2; } double solve() { double ans = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { for (int k = 1; k <= p; k++) { int x = (n - i + 1) * i; int y = (m - j + 1) * j; int z = (p - k + 1) * k; double P = (2 * x * 1.0 - 1) / (m * n * p) * (2 * y - 1) / (m * n * p) * (2 * z - 1); ans += cal(P); } } } return ans; } int main() { int cas = 0; scanf("%d", &t); while (t--) { scanf("%d%d%d%d", &n, &m, &p, &K); printf("Case %d: %.10lf\n", ++cas, solve()); } return 0; }