这是一个比赛题
(pattern.cpp/c/pas)
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。。感觉压力很大。。
f[i][j]表示前i个玩具中抽中j个不同的概率
for (int j=0;j<=n;j++) { f[i+1][j]+=f[i][j]*j/n; f[i+1][j+1]+=f[i][j]*(n-j)/n; }
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> using namespace std; float f[1005][1005]; int main() { freopen("pattern.in","r",stdin); freopen("pattern.out","w",stdout); int n,m; cin>>n>>m; f[0][0]=1; for (int i=0;i<=m-1;i++) { for (int j=0;j<=n;j++) { f[i+1][j]+=f[i][j]*j/n; f[i+1][j+1]+=f[i][j]*(n-j)/n; } } printf("%.4lf\n",f[m][n]); return 0; }
有经验就好，可以多写一写这样的题目试试看
【dp概率与期望】pattern,布布扣,bubuko.com
原文：http://www.cnblogs.com/seekdreamer/p/3857307.html