hdu 5159 Card（数学）-CSDN博客

本文链接：https://blog.csdn.net/acm_cxq/article/details/51923175

Card

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 821 Accepted Submission(s): 337
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

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

题意：有n张卡片，1~n号卡片的分数分别为1~n，从中取m次，每次取一张后放回，问期望是多少？

思路：一开始没想出来...真是太菜了。

看见这种求所有数字中取m个数字之和的所有可能性之和就应该想到1~n这n个数字是被“平等对待”的

也就是说，当我们得到所有的可能性之和的时候，1~n中的所有数字被加的次数都应该是相等的

而这个被加的次数就是n的m次方-(n-1)的m次方前者是所有的可能性，后者是不取某一个数的所有可能性（也就是说不取某一个数的所有的区间之和）

所以最终结果是(n*(n+1)/2)*(n(m)-(n-1)(m))/n(m)

n(m)表示n的m次方

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

int main()
{
    double x,b;
    int T;
    scanf("%d",&T);
    for(int t=1;t<=T;t++)
    {
        scanf("%lf %lf",&x,&b);
        double sum=x*(x+1)/2;
        sum*=pow(x,b)-pow(x-1,b);
        double sum1=pow(x,b);
        printf("Case #%d: %.3lf\n",t,sum/sum1);
    }
    return 0;
}