YYS FZU - 2278 （题解）（数学期望）

Description

Yinyangshi is a famous RPG game on mobile phones.

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. 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. Every W days, Kim can draw a card with W coins. In this problem ,we define W=(n-1)!.

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

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

题意

有 n 种卡片，每种卡片的价值是 W 个金币, xxx每天可以得到 1 个金币，从第一天开始，每天出现一张卡片，每种卡片出现的概率是 1/n ，现在xxx想得到所有的卡片，他平均需要等多少天才可以。其中 W = (n-1)!

分析： 首先看xxx需要买多少次才能得到所有的 卡片，【假设需要ans次才能得到所有的卡片】 最终需要的天数 res = ans * W 根据 UVA - 10288 Coupons 期望 （例题10-18） 我们知道 ：ans = n * ( 1 + 1/2 + 1/3 + … + 1/(n-1) + 1/n ) 那最终结果是： res = ans * W = n! * ( 1 + 1/2 + 1/3 + … + 1/(n-1) + 1/n )

代码

import java.math.BigInteger; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner cin = new Scanner(System.in); int T= cin.nextInt(); for (int t = 0; t < T; t++) { int n = cin.nextInt(); BigInteger fac = new BigInteger("1"); BigInteger ans = new BigInteger("0"); BigInteger tmp; // 1.计算 n! for(int i = 1;i <= n;i++) { tmp = new BigInteger(""+i); fac = fac.multiply(tmp); } for(int i = 1;i <= n;i++) { tmp = new BigInteger(""+i); ans = ans.add(fac.divide(tmp)); } System.out.println(ans+".0"); } } }