bzoj 2969: 矩形粉刷 概率期望+快速幂

时间：2022-05-25 06:25:44

还是老套路：期望图上的格子数=$\sum$ 每个格子被涂上的期望=$\sum$1-格子不被图上的概率

这样的话就相对好算了.

那么，对于 $(i,j)$ 来说，讨论一下上，下，左，右即可.

然后发现四个角的面积会被重复统计，所以再减去 $4$ 个角的贡献即可.

#include <bits/stdc++.h>

#define setIO(s) freopen(s".in","r",stdin)

using namespace std;

double sq(double x) { return x*x; }

int main()

{

	// setIO("input");

	int k,n,m,i,j;

	scanf("%d%d%d",&k,&n,&m);

	double ans=0.0;

	for(i=1;i<=n;++i)

	{

		for(j=1;j<=m;++j)

		{

			double a=(j-1)*n;

			double b=(m-j)*n;

			double c=(n-i)*m;

			double d=(i-1)*m;

			double d1=(i-1)*(j-1);

			double d2=(i-1)*(m-j);

			double d3=(n-i)*(j-1);

			double d4=(n-i)*(m-j);

			double tot1=(sq(a)+sq(b)+sq(c)+sq(d)-sq(d1)-sq(d2)-sq(d3)-sq(d4));

			double tot2=sq(n*m);

			// printf("%.2f\n",tot1/tot2);

			ans+=1.0-pow(tot1/tot2,k);

     	}

	}

	printf("%.0lf\n",ans);

	return 0;

}

　　

相关文章