LightOJ - 1284 Lights inside 3D Grid （概率计算）

题面：

You are given a 3D grid, which has dimensions X, Y and Z. Each of the X x Y x Z cells contains a light. Initially all lights are off. You will have K turns. In each of the K turns,

....

题意：

一个大立方体里面选择k次小的立方体，将小的立方体里面灯泡的开关按一下，问最后的小灯泡亮起的个数期望

思路：

单独计算每个点的贡献

设\(f(x)\)是一共按了x次开关，某一个小灯泡被按了奇数次的概率,\(p\)是某一次被按下的概率

其中 \(f(1) = p\)

所以，有以下公式

\[f(k)=(1-p)f(k-1)+p(1-f(k-1))
\]

化简得：

\[f(k)=(1-p)f(k-1)+p-p*f(k-1)
\]

\[f(k)=(1-2p)f(k-1)+p
\]

同理：

\[f(k-1)=(1-2p)f(k-2)+p
\]

代入\(f(k)\):

\[f(k) = (1-2p)[(1-2p)f(k-2)+p]+p
\]

\[f(k) = (1-2p)^2f(k-2)+p+p(1-p)
\]

写出\(f(k-2)\),并代入上式，可得：

\[f(k) = (1-2p)^3f(k-3)+p+p(1-p)+p(1-2p)^2
\]

...

递推可得：

\[f(k) = (1-2p)^{k-1}f(1) + p(1-2p)^{k-2}+p(1-2p)^{k-3}+...+p
\]

通过等比数列求和：

\[f(x)=(1-2p)^{k-1}*p+[1-(1-2*p)^{k-1}]/2
\]

化简得：

\[f(x) = [1-(1-2*p)^{k}]/2
\]

其中，\(p\)的计算方法为，分别计算\(x,y,z\)被选中的概率，再相乘

#include<iostream>

#include<algorithm>

#include<vector>

#include<stack>

#include<queue>

#include<map>

#include<set>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<ctime>

#define fuck(x) cout<<#x<<" = "<<x<<endl;

#define debug(a,i) cout<<#a<<"["<<i<<"] = "<<a[i]<<endl;

#define ls (t<<1)

#define rs ((t<<1)+1)

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int maxn = 100086;

const int maxm = 100086;

const int inf = 2.1e9;

const ll Inf = 999999999999999999;

const int mod = 1000000007;

const double eps = 1e-6;

const double pi = acos(-1);

double q_pow(double a,int b){

    double ans=1;

    while(b){

        if(b&1){

            ans*=a;

        }

        a*=a;

        b>>=1;

    }

    return ans;

}

double f(double p,int k){

    if(k==0){return 0;}

    double tmp = q_pow(1.0-2*p,k);

    return (1.0-tmp)/2;

}

double f1(double p,int k){

    if(k==0){return 0;}

    if(k==1){return p;}

    return (1.0-2*p)*f1(p,k-1)+p;

}

int main()

{

//    ios::sync_with_stdio(false);

#ifndef ONLINE_JUDGE

    freopen("in.txt","r",stdin);

#endif // ONLINE_JUDGE

    int T;

    scanf("%d",&T);

    int cas = 0;

    while(T--){

        int x,y,z,K;

        scanf("%d%d%d%d",&x,&y,&z,&K);

        int sum = x*y*z;

        double ans = 0;

        for(int i=1;i<=x;i++){

            for(int j=1;j<=y;j++){

                for(int k=1;k<=z;k++){

                    double p1 = 1.0-1.0*((i-1)*(i-1)+(x-i)*(x-i))/(x*x);

                    double p2 = 1.0-1.0*((j-1)*(j-1)+(y-j)*(y-j))/(y*y);

                    double p3 = 1.0-1.0*((k-1)*(k-1)+(z-k)*(z-k))/(z*z);

                    double pp = p1*p2*p3;

                    ans+=f(pp,K);

                }

            }

        }

        printf("Case %d: %f\n",++cas,ans);

    }

    return 0;

}