蓝桥杯算法训练-印章

资源限制

时间限制：1.0s   内存限制：256.0MB

问题描述

　　共有n种图案的印章，每种图案的出现概率相同。小A买了m张印章，求小A集齐n种印章的概率。

输入格式

　　一行两个正整数n和m

输出格式

　　一个实数P表示答案，保留4位小数。

样例输入

2 3

样例输出

0.7500

数据规模和约定

　　1≤n，m≤20

import java.util.Scanner;

public class T1007 {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int m = in.nextInt();
		double[][] dp = new double[m + 1][n + 1];
		double p = 1 / (double)n; //买到一种印章的概率
		for(int i = 1; i <= m; i++) {
			for(int j = 1; j <= n; j++) {
				if(i < j) {
					dp[i][j] = 0;
				}else if(j == 1){
					dp[i][j] = Math.pow(p, i - 1);
				}else {
					dp[i][j] = dp[i - 1][j] * (j * 1.0 / n) + dp[i - 1][j - 1] * (1 - (j - 1) * 1.0 / n);
				}
			}
		}
		System.out.printf("%.4f", dp[m][n]);
 }
}