BZOJ-矩阵粉刷

maxhjz · 2021-05-22 20:00:36 · 个人记录

题目描述

为了庆祝新的一年到来，小M决定要粉刷一个大木板。大木板实际上是一个W*H的方阵。小M得到了一个神奇的工具，这个工具只需要指定方阵中两个格子，就可以把这两格子为对角的，平行于木板边界的一个子矩形全部刷好。 小M乐坏了，于是开始胡乱地使用这个工具。 假设小M每次选的两个格子都是完全随机的 （方阵中每个格子被选中的概率是相等的）， 而且小M使用了K次工具，求木板上被小M粉刷过的格子个数的期望值是多少。

期望

1.期望具有可加性（线性性）

显然 答案ans=每个点被粉刷到的期望之和

但是，由于每个点被粉刷的概率不方便计算，而每个点只有两种情况（一种是被染色，另一种是不被染色），而被粉刷的概率就是1-（每次不被染色的k次方），因此我们可以计算出该点不被染色的概率，之后用1减去即是该点被染色的概率。

但是 考虑单次染色没有没染的情况：选定的两个点都在左边、上边、右边、下边，但是会发现四个角的部分会计算两次，因此还需要减掉两个点都在左上、左下、右上、右下的情况。然后求幂加起来即可。

求k次方时，可以使用C++自带的pow函数，也可以自己写一个快速幂（比用pow函数快200ms）

CODE

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
inline int read()
{
    int s=0,w=1; char ch=getchar();
    while(ch<'0'||ch>'9'){if(s=='-') w=-1; ch=getchar();}
    while(ch>='0'&&ch<='9'){s=s*10+ch-'0'; ch=getchar();}
    return s*w;
}
inline double q_pow(double x,int k)
{
    double ans=1.0;
    while(k)
    {
      if(k&1)
        ans=ans*x;
      x=x*x;
      k>>=1;
    }
    return ans;
}
inline double mi(double x)
{
    return x*x;
}
int n,k,m;
int main()
{
    k=read(),n=read(),m=read();
    double ans=0;
    for(int i=1;i<=n;i++)
    {
      for(int j=1;j<=m;j++)
      {
        double x1=mi((i-1)*m);
        double x2=mi((j-1)*n);
        double x3=mi((n-i)*m);
        double x4=mi((m-j)*n);
        double y1=mi((i-1)*(j-1));
        double y2=mi((m-j)*(n-i));
        double y3=mi((n-i)*(j-1));
        double y4=mi((m-j)*(i-1));
        double tot=mi(n*m);
        ans+=1-q_pow((x1+x2+x3+x4-y1-y2-y3-y4)/tot,k);
      }
    }
    printf("%.0lf\n",ans);
    return 0;
}