「fj夏令营」营销策略

2014年7月20日3,4850

「题目描述」
W 记的儿童套餐会赠送一份小玩具，赠送的小玩具共有 n 种。
小朋友买了 m 份儿童套餐，求收集齐 n 种小玩具的概率。假设每份儿童套餐赠送的
小玩具的种类是等概率随机的。
「输入格式」
从 pattern.in 中输入数据
一行，两个整数 n，m。
「输出格式」
输出到 pattern.out 中
一个实数表示收集齐小玩具的概率，保留 4 位小数。
「样例输入」
2 3
「样例输出」
0.7500
「数据规模与约定」
对于 10% 的数据保证：n = 1
对于 30% 的数据保证：n ≤ 2
对于 60% 的数据保证：n，m ≤ 20
对于 100% 的数据保证：1 ≤ n，m ≤ 1000

「题解」

直接dp

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,m;
double f[1005][1005];
int main()
{
    //freopen("pattern.in","r",stdin);
    //freopen("pattern.out","w",stdout);
    scanf("%d%d",&n,&m);
    f[0][0]=1;
    for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++)
		{
			f[i][j]=f[i-1][j]*((double)j/n)+f[i-1][j-1]*((double)(n-j+1)/n);
		}
    printf("%.4lf",f[m][n]);
    return 0;
}