HDU 5245 Joyful (概率期望)-蒲公英云

HDU 5245 Joyful (概率期望)

HDU 5245 Joyful (概率) ：http://acm.hdu.edu.cn/showproblem.php?pid=5245

题面描述：

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 877 Accepted Submission(s): 382

Problem Description

Sakura has a very magical tool to paint walls. One day, kAc asked Sakura to paint a wall that looks like an M×N matrix. The wall has M×N squares in all. In the whole problem we denotes (x,y) to be the square at the x-th row, y-th column. Once Sakura has determined two squares (x1,y1) and (x2,y2), she can use the magical tool to paint all the squares in the sub-matrix which has the given two squares as corners.

However, Sakura is a very naughty girl, so she just randomly uses the tool for K times. More specifically, each time for Sakura to use that tool, she just randomly picks two squares from all the M×N squares, with equal probability. Now, kAc wants to know the expected number of squares that will be painted eventually.

Input

The first line contains an integer T( T≤100), denoting the number of test cases.

For each test case, there is only one line, with three integers M,N and K.
It is guaranteed that 1≤M,N≤500, 1≤K≤20.

Output

For each test case, output ‘’Case #t:’’ to represent the t-th case, and then output the expected number of squares that will be painted. Round to integers.

Sample Input

2
3 3 1
4 4 2

Sample Output

Case #1: 4
Case #2: 8
      Hint
     The precise answer in the first test case is about 3.56790123.

题目大意：

再一个M*N的矩阵中随机涂色k次，每次涂色都是随机的选择两个点作为要涂色部分的对顶点，且涂色部分为选中部分的子区域，求经过k次染色后染色面积的期望值（四舍五入）。

题目分析：

当k等于1时，期望被染色的面积应等于每个1*1的方块被染色的期望累加之和。

设k=1时，即只染色一次时，位于第x行第y列的方块被染色的概率为A[x,y]，在经过k次操作之后，被染色的期望假设为p[x,y]，则有：p[x,y]=1-(1-A[x,y])^k

且在每次染色中可能的操作有n*n*m*m种，根据数据范围，要用long long进行存储。

代码实现：

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int main()
{
    int t,casenum=0;
    long long m,n,k;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld%lld%lld",&n,&m,&k);
        double ans=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                double p=1.0*m*n;
                p+=1.0*(i-1)*(j-1)*(n-i+1)*(m-j+1);
                p+=1.0*(i-1)*(m-j)*(n-i+1)*j;
                p+=1.0*(j-1)*(n-i)*(m-j+1)*i;
                p+=1.0*(n-i)*(m-j)*i*j;
                p+=1.0*(i-1)*m*(n-i+1);
                p+=1.0*(m-j)*n*j;
                p+=1.0*(n-i)*m*i;
                p+=1.0*(j-1)*n*(m-j+1);
                p=1.0*p/n/n/m/m;
                ans+=1-(pow(1-p,k));
            }
        }
        printf("Case #%d: %d\n",++casenum,(int)(ans+0.5));
    }
    return 0;
}