HDU 5245 Joyful 期望

题意：

给一个(M imes N)的矩形，然后随机选两个格子((x_1,y_1))和((x_2, y_2))。
这两个格子互不影响，也就是这两个格子可以相同。
以这两个格子为对角可以确定一个矩形，然后把这个矩形中的所有格子染色。
按照这样的过程一共随机选(K)个矩形将其贪色，求被染色的格子的期望。

分析：

我们单独考虑每个格子对答案的贡献，就是(K)次染色后被染中的概率。
从反面计算，对于格子((r, c))计算它一次不被染中的概率(p)，那么(K)次被染中的概率就是(1-p^K)。

总的情况数为(N^2M^2)。
要计算不被选中的情况数，就是格子((r,c))在所选的矩形外面。

所选的两个点都在((r,c))的

• 上面有((r-1)^2N^2)种情况
• 左面有(M^2(c-1)^2)种情况
• 下面有((M-r)^2N^2)种情况
• 右面有(M^2(N-c)^2)种情况

其中四个角被计重了，要再减去：

• 左上角计重了((r-1)^2(c-1)^2)
• 左下角计重了((M-r)^2(c-1)^2)
• 右下角计重了((M-r)^2(N-c)^2)
• 右上角计重了((r-1)^2(N-c)^2)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;
inline LL sqr(LL x) { return x * x; }

int main()
{
    int T; scanf("%d", &T);
    for(int kase = 1; kase <= T; kase++) {
        LL M, N, K; scanf("%lld%lld%lld", &M, &N, &K);

        LL tot = M * M * N * N;
        double ans = 0;
        for(int r = 1; r <= M; r++) {
            for(int c = 1; c <= N; c++) {
                LL t = sqr(M*(c-1)) + sqr((M-r)*N) + sqr(M*(N-c)) + sqr((r-1)*N);
                t -= sqr((r-1)*(c-1)) + sqr((M-r)*(c-1)) + sqr((M-r)*(N-c)) + sqr((r-1)*(N-c));
                double p = (double) t / tot;
                double pp = 1;
                for(int i = 1; i <= K; i++) pp *= p;
                ans += 1.0 - pp;
            }
        }

        printf("Case #%d: %.0f
", kase, ans);
    }

    return 0;
}