首页 > 代码库 > hdu 5245 Joyful(期望)

hdu 5245 Joyful(期望)

Joyful

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


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(T100), 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 1M,N5001K20.
 

 

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
23 3 14 4 2
 

 

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

 

Source
The 2015 ACM-ICPC China Shanghai Metropolitan Programming Contest
 

 

Recommend
 
 
代码较挫,
 1 #include <iostream> 2 #include <stdio.h> 3 using namespace std; 4  5 using namespace std; 6  7 #define LL long long 8  9 long long C(LL  a,LL b)10 {11     return a * b * a * b;12 }13 int main()14 {15     long long T,m,n,k;16     int cas = 0;17     scanf("%lld",&T);18     while(T--)19     {20         LL sum;21         double ans=0, p;22         scanf("%lld%lld%lld",&m,&n,&k);23         for(LL i=0; i<m; i++)24         {25             for(LL j=0; j<n; j++)26             {27                sum = C(i,n)+C((m-i-1),n)+C(j,m)+C((n-j-1),m);28                sum = sum - C(i,j) - C(i,(n-j-1)) - C((m-i-1),j ) - C((m-i-1),(n-j-1)) ;29                p = sum * 1.0 / C(m,n);30 31 double tmp=1;32                for (LL jj = 1; jj <= k; ++jj)33                     tmp *= p;34                ans=ans+1-tmp;35             }36         }37         printf("Case #%d: %.0f\n",++cas,ans);38     }39     return 0;40 }

 

hdu 5245 Joyful(期望)