这是一个 DP 题.
我们设 \(f[i][j][k]\) 表示 \(i\) 序列长度中放入了 \(j\) 个元素, 其中 \(k\) 是限定的众数的个数; 状态转移方程是
\[f[k][i][j]=f[k][i-1][j-1]+f[k][i-1][j]-f[k][i-k-1][j-1]\]
前面的两个相加应该比较好理解, 也就是我们考虑从上一个长度转移过来, 新加入的那个数是原先已经加入过的元素还是没有加入过的元素.
后面减去是因为要去掉不合法的情况 -- 如果新加入的这个数出现了 k+1 次那么就显然是不合法情况.(注:\(i-(i-k-1)=k+1\))
因为是多组数据, 但是数据范围并不大, 而且我们的答案是一步一步推出来的的, 所以针对每次询问都重新算一遍不如预处理方便. 那么我们就在询问前进行预处理.
之后就是开一个 g 数组,\(g[i]\) 表示的是众数个数小于等于 i 的时候的个数. 之后我们就可以用原先算过的 sum 数组来累加 g 的值了.
但是要注意的是, 最后一维我们不确定是那些数, 而我们又要计算序列种类个数 + 需要的是不下降的序列, 所以我们可以想到是组合数. 然后也是同样的, 考虑进行预处理. 我们预处理从 n 个里面选出来 i 个数就行了 qwq, 但是因为 n 的范围很大, 但我们需要的范围只在 m 以内, 所以预处理到 m 即可.
最后我们用出现次数乘上它的种类个数再除以总和就是期望了. 但是注意因为我们 g 数组相当于是在计算前缀和 (因为要算总数个数), 所以最后要差分.
最后注意精度问题, 我们最好使用 long double.(但是因为 long double 占用 16 个字节, 是 int 类型的 4 倍啊 qwq), 一定要注意空间是否会炸.....)
- #include<cmath>
- #include<cstdio>
- #include<cstring>
- #include<iostream>
- #include<algorithm>
- using namespace std;
- int T,m,n;
- long double C[255],sum[255][255][255],f[255][255][255],g[255];
- int main(){
- C[0]=true;
- for(register int k=1;k<=251;++k){
- sum[k][0][0]=1;
- for(register int i=1;i<=251;++i){
- for(register int j=1;j<=i;++j){
- sum[k][i][j]=sum[k][i-1][j-1]+sum[k][i-1][j];
- if(k<i) sum[k][i][j]-=sum[k][i-k-1][j-1];
- }
- }
- }
- while(cin>>m>>n){
- memset(g,0,sizeof(g));
- for(register int i=1;i<=m;++i)
- C[i]=C[i-1]*(n-i+1)/i;
- for(register int k=1;k<=m;++k)
- for(register int j=1;j<=m;++j)
- g[k]+=sum[k][m][j]*C[j];
- long double ans=0;
- for(register int k=1;k<=m;++k)
- ans+=k*(g[k]-g[k-1])/g[m];
- printf("%.4Lf\n",(double)ans);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2802569.html