Miku

用$dp_{i,j,z}$表示在第i行有j列一炮，z列二炮时的方案数

自己做的时候t飞了三个点

然后发现需要写一个更快的读入优化

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
long long dp[105][105][105];
long long mod=9999973;
long long n,m;
inline int read(){
    int ret=0,ff=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') ff=-ff;ch=getchar();}
    while(isdigit(ch)){ret=(ret<<3)+(ret<<1)+(ch^48);ch=getchar();}
    return ret*ff;
}
inline long long num(long long x){
    return ((x*(x-1))>>1)%mod;
    //一点小小的组合数学 
}
long long ans;
int main(){
    n=read();m=read();
    dp[0][0][0]=1;
    for(int i=1;i<=n;++i){
        for(int j=0;j<=m;++j)
            for(int z=0;j+z<=m&&(j+z)<=2*i;++z){
                    dp[i][j][z]+=dp[i-1][j][z];
                    dp[i][j][z]%=mod;
                    if(j)
                    dp[i][j][z]=(dp[i][j][z]+dp[i-1][j-1][z]*(m-(j-1)-z)%mod)%mod;
                    //放一个在一个一炮上 
                    if(z){
                    dp[i][j][z]=(dp[i][j][z]+dp[i-1][j+1][z-1]*(j+1)%mod)%mod;
                }
                    if(j>=2)
                    dp[i][j][z]=(dp[i][j][z]+dp[i-1][j-2][z]*num(m-(j-2)-z)%mod)%mod;
                    if(z){
                    dp[i][j][z]=(dp[i][j][z]+dp[i-1][j][z-1]*j*(m-j-(z-1))%mod)%mod;
                }
                    if(z>=2)
                    dp[i][j][z]=(dp[i][j][z]+dp[i-1][j+2][z-2]*num(j+2)%mod)%mod;
        }
    }
    for(int i=0;i<=m;++i)
        for(int j=0;i+j<=m&&(i+j)<=2*n;++j)
            ans=(ans+dp[n][i][j])%mod;
    cout<<ans;
        return 0;
}