问题描述
共有n种图案的印章，每种图案的出现概率相同。小A买了m张印章，求小A集齐n种印章的概率。
输入格式
一行两个正整数n和m
输出格式
一个实数P表示答案，保留4位小数。
样例输入
2 3
样例输出
0.7500
数据规模和约定
1≤n，m≤20
对于这道题，其本质是排列组合求概率，由题目可知当n=1时概率p为1.
当n>m时，概率p为0。因此主要分析上述两种情况之外的情况。对于买了m张印章，集齐n种印章的概率，进行以下分析：
求集齐的概率=1-集不齐的概率；
而对于购买了m种，集不齐i种的概率，可以用以下公式来进行计算：
P(集不齐i种） = P(只能集齐1种) + P(只能集齐2种）+......+P(只能集齐i-1种）
其中P(i)表示只集齐且只集齐i种，
用白话文来解释就是，对于集齐i种，即用1减去集不齐i种，而对于集不齐i种，其概率就是只集齐1种，2种，....，i-1种的概率之和。其中集齐1种的概率为1。对于抽取a个，有b种印章，只集齐c种的概率为，从b种中选出c种，为；在c种中随便选择，为
；只选到c种之中的概率，为P(k)。对于抽取a个，总共有
种可能，因此集齐只集齐c种的概率为
。
从而带入上述公式可计算。
# include<iostream>
# include<cstdio>
# include<cmath>
using namespace std;
double dp[22];
long long jiecheng(int t)
{
long long sum = 1;
for (int i=1;i<=t;i++)
sum = sum*i;
return sum;
}
long long zhuhe(int s,int r)
{
return jiecheng(s)/jiecheng(r)/jiecheng(s-r);
}
double fun(int n,int m)
{
int i,j;
double t=0;
dp[1]=1.0;
for(i=2;i<=n;i++)
{
t=0;
for(j=1;j<i;j++)
{
t=t+zhuhe(i,j)*dp[j]*pow(j,m);
}
dp[i]=1-t/pow(i,m);
}
return dp[n];
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
fun(n,m);
printf("%.4lf\n",dp[n]);
return 0;
}