1 条题解

  • 0
    @ 2021-6-15 14:11:00

    C++ :

    #include <bits/stdc++.h>
    #define N 110
    #define MAX 4500
    using namespace std;
    typedef long long ll;
    int i,j,k,n,m,x,y,t,q,la,no;
    namespace dob {typedef double db;db f[2][9005][101][3];}
    namespace fl {typedef __float128 db;db f[2][9005][101][3];}
    template <class T> inline
    void print2(T x,int k){
        for (i=2;i<=n;i++)x=x/(T)i;
        ll a=x;x-=a;int s[100],l,j=0;s[0]=0;
        while (a)s[++s[0]]=a%10,a/=10;if (!s[0])s[++s[0]]=0;l=s[0];
        for (i=1;i<=k+1;i++){x*=10;a=(int)x;x-=a;s[++s[0]]=a;}
        if (s[s[0]]>=5)j=1;int p=s[0];
        while (j&&p){s[p-1]++;j=s[p-1]/10;s[p-1]%=10;p--;}
        if (j){for (i=s[0];i>1;i--)s[i]=s[i-1];s[1]=1;}
        putchar('0'+s[1]);if (k)putchar('.');for (i=2;i<=k+1;i++)putchar(s[i]+'0');
        return;
    }
    template <class T> inline
    void solve(T f[][9005][101][3]){
        f[0][MAX-2*1][1][0]=1;f[0][MAX-1][1][1]=2;f[0][MAX][1][2]=1;no=0;la=1;
        for (int i=2;i<=n;i++){
            no=1-no,la=1-la;
            memset(f[no],0,sizeof f[no]);
            for (int j=0;j<=MAX*2;j++)
                for (int k=1;k<=n-1;k++){
                    if (f[la][j][k][0]){
                        if (j>=2*i)f[no][j-2*i][k+1][0]+=f[la][j][k][0]*(k+1);
                        if (j+2*i<=MAX*2)f[no][j+2*i][k-1][0]+=f[la][j][k][0]*(k-1);
                        f[no][j][k][0]+=f[la][j][k][0]*k*2;
                        if (j+i<=MAX*2)f[no][j+i][k][1]+=f[la][j][k][0]*2;
                        if (j>=i)f[no][j-i][k+1][1]+=f[la][j][k][0]*2;
                    }
                    if (f[la][j][k][1]){
                        if (j>=2*i)f[no][j-2*i][k+1][1]+=f[la][j][k][1]*k;
                        if (j+2*i<=MAX*2)f[no][j+2*i][k-1][1]+=f[la][j][k][1]*(k-1);
                        f[no][j][k][1]+=f[la][j][k][1]*(2*k-1);
                        if (j+i<=MAX*2)f[no][j+i][k][2]+=f[la][j][k][1];
                        if (j>=i)f[no][j-i][k+1][2]+=f[la][j][k][1];
                    }
                    if (f[la][j][k][2]){
                        if (j+i*2<=MAX*2)f[no][j+i*2][k-1][2]+=f[la][j][k][2]*(k-1);
                        if (j>=2*i)f[no][j-i*2][k+1][2]+=f[la][j][k][2]*(k-1);
                        f[no][j][k][2]+=2*f[la][j][k][2]*(k-1);
                    }
                }
        }
        T ans=0;
        for (int i=m+MAX;i<=MAX*2;i++)ans+=(T)f[no][i][1][2];
        print2(ans,q);
    }
    int main(){
        scanf("%d%d%d",&n,&m,&q);if (q<=8)solve(dob::f);else solve(fl::f);
        return 0;
    }
    
    
    • 1

    信息

    ID
    978
    时间
    6000ms
    内存
    128MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者