BZOJ2969: 矩形粉刷
题解:
我们单独考虑每个格子,如果这个格子在一次染色中不被染色的概率为p,则这个格子在k次染色中被染色的概率就是1−pk.
对于每个格子如何求p:
看着代码自己脑补一下吧= =
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | #include<cstdio>#include<cctype>#include<cstring>#include<climits>#include<iostream>#include<algorithm>#include<cmath>using namespace std; typedef double f2;typedef long long ll; ll calc(int n,int m){ return(ll)n*m*n*m;} ll C[1010][1010];int main(){ int k,w,h; cin>>k>>w>>h; ll total; f2 ans=0; for(int i=0;i<=w;++i) for(int j=0;j<=h;++j) C[i][j]=calc(i,j); for(int i=1;i<=w;++i){ for(int j=1;j<=h;++j){ total=0; total-=C[i-1][j-1]+C[i-1][h-j]+C[w-i][j-1]+C[w-i][h-j]; total+=C[w][j-1]+C[w][h-j]+C[i-1][h]+C[w-i][h]; ans+=1-pow((f2)total/C[w][h],k); } } cout<<(ll)ans+(ans-(ll)ans>=.5?1:0)<<endl; return 0;} |
评论 (0)