数学期望题（概率+递推）。注意使用大整数。
import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.io.PrintWriter; import java.math.BigInteger; import java.util.Scanner; /** * 题意：一共有 n 种不同的优惠券，得到每种优惠券的概率相同。问期望多少次可以得到所有 n 种优惠券，以带分数形式输出。 * 数据范围： 1 <= n <= 33 * * 分析：假设当前已经有 k 种优惠券，那么 p(获得新的优惠券) = (n-k)/n，所以需要步数的期望是 n/(n-k)。 * 求和得到步数的期望是 n/n+n/(n-1)+...+n/1 = n(1/n+1/(n-1)+...+1/1) = n(n!/1+n!/2+...+n!/n) / n! * * @author TinyDolphin * */ public class Main { /** * 获得分母，即：N! */ public static BigInteger getDenominator(int N) { BigInteger denominator = BigInteger.valueOf(1); for (int i = 2; i <= N; i++) { denominator = denominator.multiply(BigInteger.valueOf(i)); } return denominator; } /** * 得到分子，即：( N!/1+N!/2+N!/3+...N!/N ) * N */ public static BigInteger getMember(int N, BigInteger denominator) { BigInteger member = denominator; for (int i = 2; i <= N; i++) { member = member.add(denominator.divide(BigInteger.valueOf(i))); } return member.multiply(BigInteger.valueOf(N)); } public static void main(String[] args) { Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in))); PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out))); int inputN; BigInteger denominator; // 分母 BigInteger member; // 分子 BigInteger gcd; // 分子和分母的最大公约数 int resultInt; // 结果的整数部分 while (in.hasNext()) { inputN = in.nextInt(); denominator = getDenominator(inputN); member = getMember(inputN, denominator); gcd = member.gcd(denominator); // 用以上得到的分子和分母的最小公约数 gcd，简化分子和分母 denominator = denominator.divide(gcd); member = member.divide(gcd); // 得到最终的整数部分 resultInt = member.divide(denominator).intValue(); // 得到最终的分子 member = member.mod(denominator); if (member.intValue() == 0) { out.println(resultInt); } else { // 以下为分数的输出 // 输出分子前面的空格 int temp = resultInt; while (temp > 0) { out.print(" "); temp /= 10; } // 输出空格+分子 out.println(" " + member); // 输出整数部分+空格 out.print(resultInt + " "); // 输出分子分母之间的 ----- （"-"的数量就是分母的位数） BigInteger tempBint = denominator; while (tempBint.compareTo(BigInteger.valueOf(0)) > 0) { out.print("-"); tempBint = tempBint.divide(BigInteger.valueOf(10)); } out.println(); // 输出分母前面的空格 temp = resultInt; while (temp > 0) { out.print(" "); temp /= 10; } // 输出空格+分母 out.println(" " + denominator); } } out.flush(); } }