HDU 5159 Card （概率DP）

ゝ一纸荒年。 2022-08-22 00:03 161阅读 0赞

HDU 5159 Card （概率DP）：[http://acm.hdu.edu.cn/showproblem.php?pid=5159][http_acm.hdu.edu.cn_showproblem.php_pid_5159]

题面描述：

# Card #

**Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 802 Accepted Submission(s): 321  
Special Judge**

Problem Description

There are x cards on the desk, they are numbered from 1 to x. The score of the card which is numbered i(1<=i<=x) is i. Every round BieBie picks one card out of the x cards，then puts it back. He does the same operation for b rounds. Assume that the score of the j-th card he picks is  Sj . You are expected to calculate the expectation of the sum of the different score he picks.

Input

Multi test cases，the first line of the input is a number T which indicates the number of test cases.  
In the next T lines, every line contain x,b separated by exactly one space.  
  
\[Technique specification\]  
All numbers are integers.  
1<=T<=500000  
1<=x<=100000  
1<=b<=5

Output

Each case occupies one line. The output format is Case \#id: ans, here id is the data number which starts from 1，ans is the expectation, accurate to 3 decimal places.  
See the sample for more details.

Sample Input

2
    2 3
    3 3

Sample Output

Case #1: 2.625
    Case #2: 4.222
    
       
        
        
         
         
          Hint
        
         For the first case, all possible combinations BieBie can pick are (1, 1, 1),(1,1,2),(1,2,1),(1,2,2),(2,1,1),(2,1,2),(2,2,1),(2,2,2)
    For (1,1,1),there is only one kind number i.e. 1, so the sum of different score is 1.
    However, for (1,2,1), there are two kind numbers i.e. 1 and 2, so the sum of different score is 1+2=3.
    So the sums of different score to corresponding combination are 1，3，3，3，3，3，3，2
    So the expectation is (1+3+3+3+3+3+3+2)/8=2.625

题目大意：

从1-x中选择b个数，计算其数字不同的所有数字之和的概率。

题目分析：

要求和的期望，根据期望的基本定理：和的期望=各部分期望的和。

即：E(sum)=E(1)+E(2)+...+E(x);

考虑每一个数的贡献，b次中一个数一次都不出现的概率为(x-1)^b，而总的排列次数是x^b，所以每个数都有贡献的概率为x^b-(x-1)^b，则推广到全部，公式即为：(x^b-(x-1)^b)\*(1+2+3+...+x)/(x-1)^b=(1-((x-1)/x)^b)\*(1+x)\*x/2.

代码实现：

#include <iostream>
    #include <cstdio>
    #include <math.h>
    using namespace std;
    
    int main()
    {
        int t,x,b;
        int casenum=0;
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d%d",&x,&b);
            double a=1.0*(x-1)/x;
            a=pow(a,b*1.0);
            double ans=1-a;
            double sum=1.0*(x+1)*x/2;
            ans=sum*ans;;
            printf("Case #%d: %.3lf\n",++casenum,ans);
        }
        return 0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_5159]: http://acm.hdu.edu.cn/showproblem.php?pid=5159