1 条题解

  • 0
    @ 2023-8-25 17:43:33
    #include<bits/stdc++.h>
    #define MAXN 101
    #define MOD 9999973
    using namespace std;
    int n,m;
    long long ans=0;
    long long f[MAXN][MAXN][MAXN];
    long long C(int N)
    {
        return ((N-1)*N)/2;
    }
    void DP()
    {
        for(int i=1;i<=n;i++)
            for(int j=0;j<=m;j++)
                for(int k=0;k<=m-j;k++)
                    {
                        f[i][j][k]=f[i-1][j][k]%MOD;
                        if(j-1>=0) f[i][j][k]=(f[i][j][k]%MOD+f[i-1][j-1][k]*(m-j-k+1)%MOD)%MOD;
                        if(k-1>=0) f[i][j][k]=(f[i][j][k]%MOD+f[i-1][j+1][k-1]*(j+1)%MOD)%MOD;
                        if(j-2>=0) f[i][j][k]=(f[i][j][k]%MOD+f[i-1][j-2][k]*C(m-k-j+2)%MOD)%MOD;
                        if(k-2>=0) f[i][j][k]=(f[i][j][k]%MOD+f[i-1][j+2][k-2]*C(j+2)%MOD)%MOD;
                        if(k-1>=0) f[i][j][k]=(f[i][j][k]%MOD+f[i-1][j][k-1]*j*(m-j-k+1)%MOD)%MOD;
                    }
    }
    int main()
    {
        memset(f,0,sizeof(f));
        scanf("%d%d",&n,&m);
        f[0][0][0]=1;
        DP();
        for(int i=0;i<=m;i++)
            for(int j=0;j<=m-i;j++)
                ans=(ans%MOD+f[n][i][j]%MOD)%MOD;
        printf("%lld",ans);        
        return 0;
    }
    
    • 1

    信息

    ID
    1801
    时间
    1000ms
    内存
    64MiB
    难度
    8
    标签
    (无)
    递交数
    11
    已通过
    10
    上传者