Joyful

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

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≤100), denoting the number of test cases.

For each test case, there is only one line, with three integers

M,N and

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. 
 

这个题着实上头, 随机取两个值, 求期望值 ,完蛋求期望公式不会了0- 0 期望值高中题 ╮(╯▽╰)╭

公式不会又不是很理解 caodan

看了网上大牛的解释, 好吧

思路:

1 两层for 循环扫描每一个每一个概率相等

2 求可以覆盖的区域

这个图从大神那搞得, 以 5 为特例求覆盖5的区域根据分布原理两个相乘

1. 第一个选择 1 区域和则第二个右下 5-6-8-9 都可以

2 .第一个选择 9 区域和则第二个左上 5-4-1-2 都可以

3. 第一个选择 7 区域和则第二个右上 5-6-3-2 都可以

4 .第一个选择 3 区域和则第二个左下 5-4-7-8都可以

5. 第一个选择 2 区域和则第二个二三行 4-5-6-7-8-9 都可以

6 .第一个选择 4 区域和则第二个二三列 2-5-8-9-6-3 都可以

7 .第一个选择 8 区域和则第二个一二行 1-2-3-4-5-6 都可以

8. 第一个选择 6 区域和则第二个一二列 1-2-4-5-7-8都可以

9. 第一个选择 5 区域则第二个任意个地方都可以即 1-2-3-4-5-6-7-8-9

因此我们只需要按照上面的思路求覆盖 (x,y) 这个点 9步就可以

p=n*m;// 他自己 周围 8个方向都可以  即m*n;                    p+=(i-1)*(j-1)*(n-i+1)*(m-j+1);// 1  5-6-8-9                    p+=(i-1)*(m-j)*j*(n-i+1);//   3  4-5-7-8                    p+=(j-1)*(n-i)*i*(m-j+1);//  7  2-3-5-6                    p+=(n-i)*(m-j)*i*j;//  9   1-2-4-5                    p+=(i-1)*m*(n-i+1);// 正上  2  4-5-6-7-8-9                    p+=(m-j)*n*j;//正右  6   1-2-4-5-7-8                    p+=(n-i)*m*i;// 正下  8  1-2-3-4-5-6                    p+=(j-1)*n*(m-j+1);//正左 4  2-3-5-6-7-8

代码:

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;typedef long long ll;int main(){    int T,i,j,k;    double n,m;// n,m 要double  后面有p/(n*m*n*m) 防止误差    while(cin>>T)    {        int count=1;        while(T--)        {            scanf("%lf %lf %d",&n,&m,&k);            double p,ans=0;            for(i=1;i<=n;i++)            {                for(j=1;j<=m;j++)                {                    p=n*m;// 他自己 周围 8个方向都可以  即m*n;                    p+=(i-1)*(j-1)*(n-i+1)*(m-j+1);// 1  5-6-8-9                    p+=(i-1)*(m-j)*j*(n-i+1);//   3  4-5-7-8                    p+=(j-1)*(n-i)*i*(m-j+1);//  7  2-3-5-6                    p+=(n-i)*(m-j)*i*j;//  9   1-2-4-5                    p+=(i-1)*m*(n-i+1);// 正上  2  4-5-6-7-8-9                    p+=(m-j)*n*j;//正右  6   1-2-4-5-7-8                    p+=(n-i)*m*i;// 正下  8  1-2-3-4-5-6                    p+=(j-1)*n*(m-j+1);//正左 4  2-3-5-6-7-8                    p/=(n*n*m*m);                    ans+=1-(pow(1-p,k));                }            }            printf("Case #%d: %d\n",count++,int(ans+0.5));        }    }    return 0;}