LigthOJ1284-Lights inside 3D Grid

题意：

有一个长宽高X，Y，Z规格的灯泡空间

每次随机的去取两个坐标

使得 所有灯泡 min(x1, x2) ≤ x ≤ max(x1, x2), min(y1, y2) ≤ y ≤ max(y1, y2) ,min(z1, z2) ≤ z ≤ max(z1, z2),在此范围内的灯泡开变关、关变开。

操作k次，问起始灯泡全都是关的，最后亮的灯泡的期望

思路：

我们知道，要想一个灯泡被操作，那么它必须在选定区域中，即两个选定的灯泡在任何方向上都必须不再其同一侧

对于某个灯泡（i，j，k）,从X方向向看，两个灯选择一共X*X种，同在左边的选择有（i-1）*(i-1)种，同在右边的选择有（X-i）*(X-i)种，

那么它必须在选定区域中的概率就是

对于Y方向，Z方向也是如此

现在看经过可k次操作，该灯泡被奇数次操作的期望是对答案期望的贡献

我们发现他是（p+（1-p））^k的二项式展开的奇数项，高中记得有过类似处理提取出其奇数项

#include<bits/stdc++.h>
using namespace std;
double pp(double x,double i)
{
	return (x*x-(i-1)*(i-1)-(x-i)*(x-i))/(x*x);
}
double qf(double a,int b)
{
	double ans=1;
	while(b)
	{
		if(b&1) ans*=a;
		b>>=1;
		a*=a;
	}
	return ans;
}
int main()
{
	int T,x,y,z,t=1,k;
	double p1,p2,p3,p;
	double ans;
	scanf("%d",&T);
	while(T--)
	{
		ans=0;
		scanf("%d%d%d%d",&x,&y,&z,&k);
	    for(int i=1;i<=x;i++)
		{
			p1=pp(x,i);
	    	for(int j=1;j<=y;j++)
			{
				p2=pp(y,j);
	    		for(int kk=1;kk<=z;kk++)
		    	{
	    			p3=pp(z,kk);
	    			p=p1*p2*p3;
	    			ans+=((1-qf(1-2*p,k))/2.0);
	        	}	
	    	}	
	    }
		printf("Case %d: %.12lf\n",t++,ans);
	}
	return 0;
}