首页 > 代码库 > 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.
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.
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
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(期望)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。