uva 11605 - Lights inside a 3d Grid(概率)

本文主要是介绍uva 11605 - Lights inside a 3d Grid(概率)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：uva 11605 - Lights inside a 3d Grid

题目大意：给定一个三维坐标系大小，每个位置有一个灯，初始状态为关，每次随机选中两个点，以这两点为对角线的长方体内所有灯转变状态。操作K次，问说平均情况下，最后会有多少栈灯亮着。

解题思路：枚举坐标系上的点，计算单个点亮着的概率，然后累加即使整体的期望。对于一个点x，y，z，分别考虑每维坐标系，例如x，选中的概率为px=2∗(n−x+1)∗x−1n∗n,三维坐标均选中的概率p即为该点被选中的概率。
但是对于一点来说，因为操作K次，所以最后灯为亮的话，操作到灯的次数一定要为奇数才行，所以有∑C(iK)pi(1−p)K−i（i为奇数）
===》(1−p+p)K−(1−p−p)K2

===》1−(1−2p)K2

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>using namespace std;int N, M, P, K;inline double getp (double n, double x) {double s = n * n;double t = 2 * (n - x + 1) * x - 1;return t / s;
}inline double handle (double p) {return (1 - pow(1 - 2 * p, K)) / 2;
}double solve () {double ret = 0;for (int x = 1; x <= N; x++) {double px = getp(N, x);for (int y = 1; y <= M; y++) {double py = getp(M, y);for (int z = 1; z <= P; z++) {double pz = getp(P, z);ret += handle(px * py * pz);}}}return ret;
}int main () {int cas;scanf("%d", &cas);for (int kcas = 1; kcas <= cas; kcas++) {scanf("%d%d%d%d", &N, &M, &P, &K);printf("Case %d: %.10lf\n", kcas, solve());}return 0;
}