[ahoi2009]chess Chinese chess - combination number optimization shape pressure DP

Topic link

Excerpt from ：
Dream_Maker_yangkai
link

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define int long long
const int N = 110,mod = 9999973;
int f[N][N][N];
int C[N][N];
int n,m;
signed main()
{
    
    cin>>n>>m;
    for(int i=0;i<N;i++){
    
        for(int j=0;j<=i;j++){
    
            if(!j)C[i][j]=1;
            else C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
        }
    }
    if(n<m)swap(n,m);
    f[0][0][0]=1;
    //f[i][j][k] To i That's ok , Yes j Listed 1 Number ,k Listed 2 The number of schemes .
    for(int i=1;i<=n;i++)
    {
    
        for(int j=0;j<=m;j++)
        {
    
            for(int k=0;k<=m-j;k++)
            {
    
                int &v=f[i][j][k];
                // Choose nothing 
                v=f[i-1][j][k];
                // The first i OK, let's go 1 individual   Put the quantity as 0 On the list of 
                if(j)v=(v+f[i-1][j-1][k]*C[m-j-k+1][1]%mod)%mod;
                // The first i OK, let's go 1 individual   Put the quantity as 1 On the list of 
                if(k>=1&&j<=m-1)v=(v+f[i-1][j+1][k-1]*C[j+1][1]%mod)%mod;
                // The first i OK, let's go 2 individual   Put them into two quantities respectively 0 On the list of 
                if(j>=2)v=(v+f[i-1][j-2][k]*C[m-j-k+2][2]%mod)%mod;
                // The first i OK, let's go 2 individual   Put them in a quantity of 0 and 1 On the list of 
                if(j&&k)v=(v+f[i-1][j][k-1]*j%mod*(m-j-k+1)%mod)%mod;
                // The first i OK, let's go 2 individual   Put them into two quantities respectively 1 On the list of 
                if(k>=2&&j<=m-2)v=(v+f[i-1][j+2][k-2]*C[j+2][2]%mod)%mod;
            }
        }
    }
    int res=0;
    for(int i=0;i<=m;i++)
        for(int j=0;j<=m-i;j++)
            res=(res+f[n][i][j])%mod;
    cout<<res<<endl;
}