为了庆祝新的一年到来,小M决定要粉刷一个大木板。大木板实际上是一个W*H的方阵。小M得到了一个神奇的工具,这个工具只需要指定方阵中两个格子,就可以把这两格子为对角的,平行于木板边界的一个子矩形全部刷好。小M乐坏了,于是开始胡乱地使用这个工具。
假设小M每次选的两个格子都是完全随机的(方阵中每个格子被选中的概率是相等的),而且小M使用了K次工具,求木板上被小M粉刷过的格子个数的期望值是多少。
str using -i 需要 int scrip stream 新的
题解:跟染色那题一样,由于期望可加,所以我们只需要统计每个点被刷到的概率。而每个点被刷到的概率=1-每个点没被刷到的概率,没被刷到的怎么算呢?维护个二位前缀和,然后容斥搞一搞就行了。
- #include <cstdio>
- #include <cstring>
- #include <iostream>
- using namespace std;
- typedef long long ll;
- int K,W,H;
- double ans;
- double pm(double x,int y)
- {
- double ret=1;
- while(y)
- {
- if(y&1) ret=ret*x;
- x=x*x,y>>=1;
- }
- return ret;
- }
- inline ll c(ll x)
- {
- return x*x;
- }
- int main()
- {
- int i,j;
- scanf("%d%d%d",&K,&W,&H);
- for(i=1;i<=W;i++)
- {
- for(j=1;j<=H;j++)
- {
- ans+=pm((double)(c((i-1)*H)+c((j-1)*W)+c((W-i)*H)+c(W*(H-j))-c((i-1)*(j-1))-c((i-1)*(H-j))-c((W-i)*(j-1))-c((W-i)*(H-j)))/c(W*H),K);
- }
- }
- printf("%.0lf",W*H-ans);
- return 0;
- }
【BZOJ2969】矩形粉刷 概率+容斥
来源: http://www.bubuko.com/infodetail-2313001.html