【0】题解：P2051 [AHOI2009] 中国象棋

· · 题解 

f[i][j][k] 前 i 行，j 列 1 个，k 列 2 个

f[i][j][k]
    f[i-1][j][k]
f[i][j][k]
    f[i-1][j+1][k-1]*(j+1)
    f[i-1][j-1][k]*(m-(j-1)-k)
f[i][j][k]
    f[i-1][j-2][k]*C(m-(j-2)-k,2)
    f[i-1][j][k-1]*(m-j-(k-1))*j
    f[i-1][j+2][k-2]*C(j+2,2)

上面是做题时的笔记。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e2+10;
const ll P=9999973;
int n,m;
ll f[N][N][N],C2[N];
int main(){
    cin>>n>>m;
    for(int i=2;i<=m;i++)
        C2[i]=(i*(i-1)/2)%P;
    f[0][0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            for(int k=0;j+k<=m;k++){
                               (f[i][j][k]+=f[i-1][j][k])%=P;
                if(j!=m&&k!=0) (f[i][j][k]+=f[i-1][j+1][k-1]*(j+1)%P)%=P;
                if(j!=0)       (f[i][j][k]+=f[i-1][j-1][k]*(m-(j-1)-k)%P)%=P;
                if(j>=2)       (f[i][j][k]+=f[i-1][j-2][k]*C2[m-(j-2)-k])%=P;
                if(k>=1)       (f[i][j][k]+=f[i-1][j][k-1]*(m-j-(k-1))%P*j%P)%=P;
                if(j-1<m&&k>=1)(f[i][j][k]+=f[i-1][j+2][k-2]*C2[j+2]%P)%=P;
            }
        }
    }
    ll ans=0;
    for(int j=0;j<=m;j++)for(int k=0;j+k<=m;k++)
        ans=(ans+f[n][j][k])%P;
    cout<<ans;
    return 0;
}