M_sea

UVA11605 Lights inside a 3d Grid
UVaLuoguVjudge分析设 $f_{i,j}$ 表示 $j$ 次操作后点 $i$ 为 $1$ 的概率。因为...
扫描右侧二维码阅读全文
30
2019/08

UVA11605 Lights inside a 3d Grid

UVa

Luogu

Vjudge

分析

设 $f_{i,j}$ 表示 $j$ 次操作后点 $i$ 为 $1$ 的概率。因为各点独立,所以答案为 $\displaystyle\sum f_{i,K}$ 。

考虑如何计算 $f_{i,j}$ 。设 $p_i$ 为点 $i$ 在范围内的概率,可以写出式子

$$ f_{i,j}=f_{i,j-1}\times(1-p_i)+(1-f_{i,j-1})\times p_i $$

化简后得到

$$ f_{i,j}=f_{i,j-1}\times(1-2p_i)+p_i $$

进一步得到

$$ f_{i,j}=0.5-\frac{(1-2p_i)^j}{2} $$

于是只要考虑如何计算 $p_i$ 即可。

设 $i$ 的坐标为 $(x,y,z)$ ,$g(i,n)$ 表示在 $1\sim n$ 内两个随机变量 $x,y$ 满足 $\min(x,y)\leq i\leq\max(x,y)$ 的概率。

那么容易得到

$$ p_i=\frac{g(x,n)\times g(y,m)\times g(z,p)}{(nmp)^2} $$

于是只要考虑如何计算 $g(i,n)$ 即可,容易得到

$$ g(i,n)=n^2-(i-1)^2-(n-i)^2 $$

然后就做完了。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

inline double f(int l,int r) {
    return r*r-(l-1)*(l-1)-(r-l)*(r-l);
}

int main() {
    int T=read();
    for (re int _=1;_<=T;++_ ){
        int n=read(),m=read(),p=read(),K=read(); double ans=0;
        for (re int i=1;i<=n;++i)
            for (re int j=1;j<=m;++j)
                for (re int k=1;k<=p;++k) {
                    double P=f(i,n)*f(j,m)*f(k,p)/(n*m*p)/(n*m*p);
                    ans+=0.5-pow(1-2*P,K)/2;
                }
        printf("Case %d: %.10lf\n",_,ans);
    }
    return 0;
}
最后修改:2019 年 08 月 30 日 05 : 04 PM

发表评论