Statement

[P2051 AHOI2009]中国象棋 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

Solution

显然的性质是，同一行列不能放两个以上的棋子

问题在于如何处理行列的关系，不妨把行拎出来考虑

假设我们正在填写第 \(i\) 行，发现我们只需要知道有多少个列没有填，多少个列填了一个，多少个列填了两个（满了）就可以进一步填写了（不必知道具体填写方案）。

设 \(f[i][j][k]\) 表示前 \(i\) 行，\(j\) 列填了一个棋子，\(k\) 列填了两个棋子的方案数

此时，有 \(m-j-k\) 列什么也没有填，考虑状态转移

不填 \(f[i][j][k]=f[i-1][j][k]\)

填 1 个

\[f[i][j][k]=\left\{ \begin{array}{l} f[i-1][j+1][k-1]\times (j+1), &填在放了一个的列\\ f[i-1][j-1][k] \times (m-j-k+1),&填在本来就没有的列 \end{array} \right. \]

填 2 个

\[f[i][j][k]=\left\{ \begin{array}{l} f[i-1][j-2][k]\times \tbinom{m-j-k+2}{2},&全部填在本来就没有的列\\ f[i-1][j][k-1]\times j\times (m-j-k+1),&一个填在没有，一个填在有一个\\ f[i-1][j+2][k-2]\times \tbinom{j+2}{2},& 全部填在放了一个的列\\ \end{array} \right. \]

注意到放了两个的列显然不能再放，一行最多放两个

初状态 \(f[0][0][0]=1\)

答案 \(\sum_{i=0}^m\sum_{j=0}^{i+j\leq\max(m,2n)}f[n][i][j]\)

状态数 \(O(n^3)\) ，转移 \(O(1)\) 时间复杂度 \(O(n^3)\)

只用到 \(f[i],f[i-1]\) ，空间 \(O(n^2)\)

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 105;
const int mod = 9999973;

int f[N][N][N];
int n,m,ans;

int C(int x){return (x*(x-1)/2)%mod;}

signed main(){
    scanf("%lld%lld",&n,&m);
    f[0][0][0]=1;
    for(int i=1;i<=n;++i)
        for(int j=0;j<=m;++j)
            for(int k=0;k<=m-j;++k){
                f[i][j][k]=f[i-1][j][k];
                if(k>=1)(f[i][j][k]+=f[i-1][j+1][k-1]*(j+1))%=mod;
                if(j>=1)(f[i][j][k]+=f[i-1][j-1][k]*(m-j-k+1))%=mod;
                if(j>=2)(f[i][j][k]+=f[i-1][j-2][k]*C(m-j-k+2))%=mod;
                if(k>=1)(f[i][j][k]+=f[i-1][j][k-1]*j*(m-j-k+1))%=mod;
                if(k>=2)(f[i][j][k]+=f[i-1][j+2][k-2]*C(j+2))%=mod;
            }
    int ans=0;
    for(int i=0;i<=m;++i)
        for(int j=0;j<=m;++j)
            (ans+=f[n][i][j])%=mod;
    printf("%lld\n",ans);
    return 0;
}