序列（DP）（组合数）

这是一个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;

}

巴特西

序列（DP）（组合数）

最新文章

热门文章