这是n^2 *m 的dp

#include<iostream>
#include <cstring>
using namespace std ;
#define int long long
int mod;
int n,m,fac[503],f[5008][500];
 // f[i][j] =max{f[k][j-1]+1 } j<i-1

 void sov(){

    f[0][0]=1;
    for(int i=1;i<=n;i++) f[1][i]=f[0][i]=1;

    for(int i=1;i<=m;i++){
         for(int j=i;j<=n;j++)
         for(int k=0;k<j-1;k++)
            f[i][j]+=f[i-1][k],f[i][j]%=mod;
    }   
    cout<< (f[m][n]* fac[m])%mod <<endl;
 }
 signed main(){
    int i,ty; 
    cin>>ty>>n>>m>>mod;

    fac[0]=1;
    for(i=1;i<=500;i++) fac[i]=fac[i-1]*i,fac[i]%=mod;

    sov();
 }

以下是有问题的前缀和优化:

#include<iostream>
#include <cstring>
using namespace std ;
#define int long long
int mod;
int n,m,fac[2002],f[2002][2002],s[2002][2002];
 

 void solve(){
    int i,j;
    s[0][0]=f[0][0]=1;
    for(i=1;i<=n;i++){
        f[1][i]=f[0][i]=1;
        s[1][i]=s[1][i-1]+f[1][i];
        s[0][i]=s[0][i-1]+f[0][i];
    }

    for(i=1;i<=m;i++)
         for(j=i;j<=n;j++){
            if(j>=2) f[i][j]=s[i-1][j-2] ;

            s[i][j]=s[i][j-1]+f[i][j],s[i][j]%=mod ;
         }

    cout<< (f[m][n]* fac[m])%mod <<endl;
 }
 signed main(){
    int i,ty; 
    cin>>ty>>n>>m>>mod;

    fac[0]=1;
    for(i=1;i<=2000;i++) fac[i]=fac[i-1]*i,fac[i]%=mod;

    solve();
 }