收集卡牌（期望递推+高精度） - FZU 2278

第八届福建省大学生程序设计竞赛FZU2278 YYS

Problem Description

Yinyangshi is a famous RPG game on mobile phones.

Yinyangshi是一款有名的手机RPG游戏。

Kim enjoys collecting cards in this game. Suppose there are n kinds of cards. If you want to get a new card, you need to pay W coins to draw a card.

Kim喜欢在这场比赛中收集牌。 假设有n种卡片。 如果你想获得一张新卡，你需要支付W币来抽一张卡。

Each time you can only draw one card, all the cards appear randomly with same probability 1/n. Kim can get 1 coin each day. Suppose Kim has 0 coin and no cards on day 0.

每次只能抽一张牌时，所有牌都会以1 / n的概率随机出现。 Kim每天可以获得1枚硬币。 假设Kim在第0天有0枚硬币而没有牌.

Every W days, Kim can draw a card with W coins. In this problem ,we define W=(n-1)!.

每隔W天，Kim就可以用W币画一张牌。

Now Kim wants to know the expected days he can collect all the n kinds of cards.

现在Kim想知道他可以收集所有n种卡的预期天数。

Input

The first line an integer T(1 ≤ T ≤ 10). There are T test cases.

The next T lines, each line an integer n. (1≤n≤3000)

Output

For each n, output the expected days to collect all the n kinds of cards, rounded to one decimal place.

Sample Input

4 1 2 5 9

Sample Output

1.0 3.0 274.0 1026576.0

思路

题意要求期望天数，但是我们知道：期望天数 = 期望次数

考虑当我们已经抽到K张卡，我们还需要抽多少次才能抽到

张卡的期望？ 答案是：

。抽到新卡概率是：

. 对于事件A，期望等于概率的倒数：

.

这个应该很好理解，比如抛一枚硬币有1/2可能性正面向上，问你抛出正面向上的期望次数是多少？当然是2次呀。

所以：

递推一下就有期望次数：

.

答案就是

。暴力算就可以了。

到了这里这个题的难度就在于3000的阶乘爆longlong了，__int128也不行。

所以要么敲大整数模板要么用Java。当然选择Java呀。不过平时准备一个大数模板也挺好的。

虽然化简的公式有调和级数，但是我们不用求它，因为在每一项乘了n!后它肯定是整数啦。

不过我还是提一下调和级数的求法：

当n小于10000时，暴力求:

当n大于10000时，它的值收敛于:

; (c是欧拉常数)

c = 0.57721566490153286060651209

Java代码

import java.io.*;
import java.math.*;
import java.util.*;
import java.math.BigInteger;
import java.io.PrintStream;
import java.util.Arrays;
import java.util.Scanner;


public class Main{

    static PrintStream putOut = System.out;
    static BigInteger pw[] = new BigInteger[3005];
    static BigInteger ans[] = new BigInteger[100005];

    static double c=0.57721566490153286060651209;
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        pw[0] = BigInteger.valueOf(1);pw[1]=pw[0];
        for(int i=2;i<=3000;++i){
            pw[i] = pw[i-1].multiply(BigInteger.valueOf(i));
        }
        int tim = cin.nextInt();
        for(int t=0;t<tim;++t){
            int n = cin.nextInt();
            BigInteger tmp  = new BigInteger("0");
            tmp = BigInteger.valueOf(n);
            tmp = tmp.multiply(pw[n-1]);
            BigInteger ans  = BigInteger.valueOf(1),hh=tmp;
            tmp = BigInteger.valueOf(0);
            for(int i=1;i<=n;++i){
                tmp = tmp.add(hh.divide(BigInteger.valueOf(i)));
            }
            putOut.println(tmp+".0");
        }

    }
}