首页 > 代码库 > HDU 5159 Card( 计数 期望 )

HDU 5159 Card( 计数 期望 )

2024-10-31 08:43:39   211人阅读

Card

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 191    Accepted Submission(s): 52
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，2So the expectation is (1+3+3+3+3+3+3+2)/8=2.625
 
 
我的做法是把它想象成一棵 m 层的 x 叉树（底层有 x^b 个叶子结点）， 然后计算每个数字（1~x ）要加的次数。
对于( i = 1 ~  x ) ..  
在第1层就要加 x^( m-1 ) 次 。
第2层就要加 x^(m-2) *(x-1) 次 。
....
第 i 层就要加 x^( m - i ) * (x-1)^( i - 1 )。
....
第m层就要加 x^(0) *（x-1)^(m-1) 次。
 
 以 i = 1 为例 ，如下图：
技术分享
 
那么每个数加的次数就是  x^i * ( x - 1 )^( m - i - 1 ) 次 [ 0 <= i < m ]。
总共加的和 sum = sigma(j) * x^i * ( x - 1 )^( m - i - 1 ) 次 [ 1<=j <= x , 0 <= i < m ]。
sigma(j) [1<=j <= x ] = (1+x)*x/2。
那么 sum = (1+x) * x / 2 * x^i * ( x - 1 )^( m - i - 1 ) , [ 0 <= i < m ] 。 
那么期望 Ex = sum / ( x ^ n ) 。
 
 
官方题解是给出普通用概率方法求 ：
设Xi代表分数为i的牌在b次操作中是否被选到,Xi=1为选到，Xi=0为未选到那么期望EX=1*X1+2*X2+3*X3+…+x*XxXi在b次中被选到的概率是1-(1-1/x)^b那么E(Xi)= 1-(1-1/x)^b那么EX=1*E(X1)+2*E(X2)+3*E(X3)+…+x*E(Xx)=(1+x)*x/2*(1-(1-1/x)^b)

技术分享
#include <iostream>#include <cstdio>#include <cstring>#include <string>#include <cmath>#include <vector>#include <queue>#include <map>#include <set>#include <stack>#include <algorithm>using namespace std;#define root 1,n,1#define lson l,mid,rt<<1#define rson mid+1,r,rt<<1|1#define lr rt<<1#define rr rt<<1|1typedef long long LL;typedef pair<int,int>pii;#define X first#define Y secondconst int oo = 1e9+7;const double PI = acos(-1.0);const double eps = 1e-6 ;const int N = 100010;double n ;int m ;void Run() {    scanf("%lf%d",&n,&m);    double avg = ( 1.0 + n ) * n / 2.0 * pow( 1.0 / n , (double) m ) , res = 0 ;    for( int i = 0 ; i < m ; ++i ) {        res += avg * pow( n - 1.0 , (double)i )*pow( (double)n, m-i-1.0 );    }    printf("%.3lf\n",res);}int main(){    #ifdef LOCAL        freopen("in.txt","r",stdin);    #endif // LOCAL    ios::sync_with_stdio(false);    int _ , cas = 1 ; scanf("%d",&_);    while( _-- ){        printf("Case #%d: ",cas++); Run();    }}
View Code

 

 

HDU 5159 Card( 计数 期望 )


联系
我们