ALOG01 印章

试题 算法训练 印章

import java.util.Scanner;

/**
 * @author HuaWang135608
 * @date 2023.03.10 16:34:11
 * @description [试题 算法训练 印章](https://lx.lanqiao.cn/problem.page?gpid=T3002)
 * 参考：https://blog.csdn.net/okok__TXF/article/details/121099645
 */

public class A1007_Seal {

	public static void main(String[] args) {
		try (Scanner sc = new Scanner(System.in)) {
			// 数据输入
			int n = sc.nextInt(); // 图案数量
			int m = sc.nextInt(); // 购买数量
			// 此矩阵中的每个元素表示：买 i 块共有 j 种图案的概率（i、j 均为下标）
			double[][] probability = new double[m + 1][n + 1];
			double res;

			// 数据处理
			for (int i=1; i<=m; ++i) {
				// 买 i 块共有 1 种图案的概率为 1 / (n^(i-1)
				// 因为买第 1 块必然是一种：probability[1][1] = 1
				probability[i][1] = Math.pow(1.0 / n, i - 1);
				
				for (int j=2; j<=i && j<=n; ++j) {
					// 其它则是两种情况
					probability[i][j] = 
							probability[i - 1][j - 1] * (1.0 - (j - 1.0) / n)
							+ probability[i - 1][j] * (1.0 * j / n);
					// 若 i - 1 块集齐了 j - 1 种图案，
					// 则需要第 j 块抽中剩下的 (n - j + 1) 中的一种
					// 为：probability[i-1][j-1] * (n - j + 1) / n
					// 
					// 若 i - 1 块集齐了 j 种图案，
					// 则需要第 j 块抽中这 j 种图案之一
					// 为：probability[i - 1][j] * j / n
				}
				
				// 若买的数量比需要的种类要小，则不可能集齐
				for (int j=i+1; j<=n; ++j) {
					probability[i][j] = 0;
				}
			}
			res = probability[m][n];
			

			// 结果输出
			System.out.printf("%.04f", res);
		}
	}

}