【蓝桥杯 印章】

题目

题目很简单，就是m张印章中集齐n种印章的概率。需要用到动态规划，，动态规划首先先考虑运用一维数组还是二维数组，本题有两个变量就使用二维数组。之后考虑初始情况，设j种i个，考虑初始情况，当只有1种印章时，j=1,i=1,dp[i][j]=1,i>1,dp[i][j]=(1/n)^(i-1),意思就是买 i 张凑齐 1 种印章的概率，意味着买的这 i 张印章是同一种，概率就是 (1/n)^i，但是，我们这 i 张要么是第一种，要么是第二种…( 要么是第k种 ，1 <= k <= n )。最后还要乘上n，所以这个情况 dp[i] [j] = (1/n)^(i-1).然后考虑中间情况，如果j>i，则永远不可能有收集齐的情况。

剩下的又分为两种情况，一种是第i次抽到的是之前已经有的印章，这种时候的概率就是dp[i][j]=dp[i-1][j]*(j/n);前一次的概率乘本次的概率。另一种是抽到的是j种正好差的那一种，这时候的概率是dp[i][j]=dp[i-1][j-1]*(n-(j-1))/n;同样也是前一次乘本次的概率。

不懂移步这条

#include
#define ll long long
using namespace std;
const ll maxn=50;
const ll mod=10007;
const double pi=acos(-1);

int main()
{
	int n,m;
	cin>>n>>m;
	double dp[50][50];
	double p=1.0/n;
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(i