SGU385 Highlander

题目来源:SGU 385
图片来自国家集训队论文《浅析竞赛中一类数学期望问题的解决方法》

其中min(j,i-j+1) 更改为min(j-1,i-j)貌似更合适。

#include<bits/stdc++.h>

using namespace std;

double d[105];
double fac[105];
double f[105][105][105];
double g[105][105];

double A(int i,int j){
    return fac[i]/fac[i-j];
}

int main(){
    int n;
    scanf("%d",&n);

    fac[0]=1;
    for(int i=1;i<=n;++i){
        fac[i]=i*fac[i-1];
    }

    d[1]=0,d[2]=1;
    for(int i=3;i<=n;++i){
        d[i]=(i-1)*(d[i-1]+d[i-2]);
    }

    for(int i=2;i<=n;++i){
        for(int j=2;j<i;++j){
            for(int l=2;l<=min(j-1,i-j);l++){
                f[i][j][1]+=g[i-j][l];
            }
            f[i][j][1]*=A(n-i+j,j)/j;
            g[i][j]+=f[i][j][1];
            for(int k=2;k<=i/j;k++){
                f[i][j][k]=f[i-j][j][k-1]*A(n-i+j,j)/j/k;
                g[i][j]+=f[i][j][k];
            }
        }
        f[i][i][1]=A(n,i)/i;
        g[i][i]+=f[i][i][1];
    }

    double res=0;
    for(int j=2;j<=n;++j){
        for(int k=1;k<=n;++k){
            res+=f[n][j][k]*j*k;
        }
    }
    printf("%.10f\n",res/d[n]);

    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注