AHOI2009 中国象棋

题目链接

题解

不好形容的DP。设$f(i,j,k)$表示当前在第$i$行，有$j$列没炮，$k$列$1$个炮。就可以愉快的转移了。
转移的时候注意系数。（也就是组合数）

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 2000000000
#define Mod 9999973ll
using namespace std;
typedef long long ll;
int read(){
    int f=1,x=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return f*x; 
}
ll n,m,f[105][105][105]={0};
//f(i,j,k) 第i行 j列0个 k列1个 
void init(){
    n=read(),m=read();
    f[1][m][0]=1,f[1][m-1][1]=m;
    if(m!=1)f[1][m-2][2]=m*(m-1)/2;
}
void solve(){
    for(int i=2;i<=n;i++)
        for(ll j=0;j<=m;j++)
            for(ll k=0;k+j<=m;k++){
                f[i][j][k]+=f[i-1][j][k];
                
                if(k>=2)f[i][j][k]+=f[i-1][j+2][k-2]*(j+2)*(j+1)/2;
                if(j+1<=m)f[i][j][k]+=f[i-1][j+1][k]*(j+1)*k;
                if(k+2<=m)f[i][j][k]+=f[i-1][j][k+2]*(k+2)*(k+1)/2;
                
                if(k>=1)f[i][j][k]+=f[i-1][j+1][k-1]*(j+1);
                if(k+1<=m)f[i][j][k]+=f[i-1][j][k+1]*(k+1);
                
                f[i][j][k]%=Mod;
            }
    ll ans=0;
    for(int j=0;j<=m;j++)
        for(int k=0;k+j<=m;k++)
            ans=(ans+f[n][j][k])%Mod; 
    printf("%lld\n",ans);
}
int main(){
    init();
    solve();
    return 0;
}