1 #include
     
       2 #include
      
        3 int main() 4 { 5     double ans; 6     int n; 7     while(~scanf("%d",&n)){ 8         if(n<10000){ 9             ans=0.0;10             for(int i=1;i<=n;i++)11                 ans+=1.0*n/i;12             printf("%lld\n",(long long)(ans+0.5));13         }else{14             printf("%lld\n",(long long)(n*(log(n+1)+0.5772156649)));15         }16     }17     return 0;18 }
      
     

收集一种卡片的概率为1，然后再买一袋即可

收集2种的概率(n-1)/n,所以期

望为n/(n-1)

依次类推，得到所有的期望为:

f[n_] := Sum[n/k, {k, 1, n}]

上式可以优化，利用高数学的基数，Ln(n)=(1+1/2+1/3+....+1/n),可以精简为

n*(Ln(n)+0.5772156649) 其中常数为欧拉常数

最后注意前面当n不是很大的时候不能用公式!

本题WA无数次，最后经南工ACM群中大神指点和聪神的测试数据才得以AC!