BZOJ2969: 矩形粉刷

题解:

我们单独考虑每个格子,如果这个格子在一次染色中不被染色的概率为$p$,则这个格子在$k$次染色中被染色的概率就是$1-p^k$.

对于每个格子如何求$p$:

看着代码自己脑补一下吧= =

代码:

#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;
}