首页 > 代码库 > NOI模拟(3.6)Assignment

NOI模拟(3.6)Assignment

2024-09-07 13:34:56   215人阅读

Description

随机生成一个长度为m且每个元素都为1~n之间的整数的单调不下降序列技术分享~技术分享(即序列的技术分享(i>1)都不小于技术分享)，（随机生成指每一种可能的序列都等概率被生成）。请问这个序列的众数出现次数期望是多少，有多组数据。
 

Input

第一行一个整数T，为数据组数
接下来T行，每行两个被空格隔开的正整数m,n为序列长度和元素的值的上界。

Output

一共T行，每一行一个实数，为每组数据的答案
如果你的答案与标准答案的误差不超过1e-5，则视为正确
 

Sample Input

4
1 5
3 3
2 9
9 6

Sample Output

1.0000000000
2.2000000000
1.2000000000
4.3146853147
 

Data Constraint

对于10%的数据：n，m<=5，T=1
对于另外20%的数据：m<=15，T<=5
对于另外20%的数据：n,m<=50, T<=5
对于100%的数据：1<=m<=250，1<=n<=1e9，T<=15
 

Hint

对于3 3这一组数据，有以下情况(x为众数出现的次数)
1 1 1 (x = 3) 
1 1 2 (x = 2) 
1 1 3 (x = 2) 
1 2 2 (x = 2) 
1 2 3 (x = 1) 
1 3 3 (x = 2) 
2 2 2 (x = 3) 
2 2 3 (x = 2) 
2 3 3 (x = 2) 
3 3 3 (x = 3) 
所以期望是1/10+2*6/10+3*3/10=22/10

Solution

看看应该是一道dp

可以有这样一个思路

令f(i,j)为构造出的序列长度为i，当前填入序列第j种数，为了限制众数的出现次数，要去除所有众数出现次数大于限定的情况

因此，f(k,i,j)=f(k,i-1,j-1)+f(k,i-1,j)-f(k,i-k-1,j-1)，其中k代表限定众数出现次数为k

最后乘上一个组合数就是答案了

#include <stdio.h>#include <string.h>template<class T> inline void read(T &x)	{	int c=getchar();	for(x=0;c<48||c>57;c=getchar());	for(;c>47&&c<58;c=getchar())x=(x<<1)+(x<<3)+c-48;	}int T,m,n;long double C[255],f[255][255][255],g[255],ans;int main()	{	freopen("assignment.in","r",stdin);	freopen("assignment.out","w",stdout);	for(int k=1;k<=250;k++)		{		f[k][0][0]=1;		for(int i=1;i<=250;i++)			for(int j=1;j<=i;j++)				{				f[k][i][j]=f[k][i-1][j-1]+f[k][i-1][j];				if(i-k-1>=0)f[k][i][j]-=f[k][i-k-1][j-1];				}		}	for(read(T);T;T--)		{		read(m),read(n);		C[0]=1;		for(int i=1;i<=m;i++)			C[i]=C[i-1]*(n-i+1)/i;		for(int k=1;k<=m;k++)			{			g[k]=0;			for(int j=1;j<=m;j++)				g[k]+=f[k][m][j]*C[j];			}		ans=0;		for(int k=1;k<=m;k++)			ans+=k*(g[k]-g[k-1])/g[m];		printf("%.6f\n",(double)ans);		}	fclose(stdin);	fclose(stdout);	return 0;	}

　　

NOI模拟(3.6)Assignment


联系
我们