中 国 象 棋 中国象棋 中国象棋

题目描述见链接 .

<mstyle mathcolor="grey"> 最 初 想 法 </mstyle> \color{grey}{最初想法} 最初想法

  • 可以发现每行每列最多只能够放 2 2 2 个棋子 .

设 F [ i , j , a , b ] F[i, j, a, b] F[i,j,a,b] 表示前 i i i 行,前 j j j 列,第 i i i 行放置了 a a a 个棋子, 第 j j j 列放置 b b b 个棋子的方案数, 发现不可行.

<mstyle mathcolor="red"> 正 解 部 分 </mstyle> \color{red}{正解部分} 正解部分

  • 发现可以不用关心棋子的顺序 .

设 F [ i , j , k ] F[i, j, k] F[i,j,k] 表示前 i i i 行, 有 j j j 列放了 1 1 1 个棋子, k k k 列放了 2 2 2 个的方案数,

为什么这样设状态? 因为这样设状态可以方便的得知放 0 0 0 个棋子的列数是 M − j − k M-j-k M−j−k .

考虑按行转移:

  • 第 i i i 行放 1 1 1 个棋子, <mstyle mathcolor="red"> # </mstyle> \color{red}{\#} #
    F [ i , j , k ] = F [ i − 1 , j + 1 , k − 1 ] + F [ i − 1 , j − 1 , k ] F[i, j, k] = F[i-1, j+1,k-1] + F[i-1,j-1,k] F[i,j,k]=F[i−1,j+1,k−1]+F[i−1,j−1,k] .

  • 第 i i i 行放 2 2 2 个棋子, <mstyle mathcolor="red"> # </mstyle> \color{red}{\#} #
    F [ i , j , k ] = F [ i − 1 , j − 2 , k ] + F [ i − 1 , j , k − 1 ] + F [ i , j + 2 , k − 2 ] F[i, j, k] = F[i-1,j-2,k]+F[i-1,j,k-1]+F[i,j+2,k-2] F[i,j,k]=F[i−1,j−2,k]+F[i−1,j,k−1]+F[i,j+2,k−2] .

  • 不放棋子, (这个容易忘记) .
    F [ i , j , k ] = F [ i − 1 , j , k ] F[i, j, k] = F[i-1, j, k] F[i,j,k]=F[i−1,j,k] .

到这里, 相信已经有人发现了不对的地方, 上面标红色井号的方程是不是显得有些太简单了 …
原来是状态的转移没考虑到全部情况, 即有多种方式从 i − 1 i-1 i−1 行的状态到 i i i 行状态,
下面重新写一遍状态转移方程,

  • 第 i i i 行放 1 1 1 个棋子, <mstyle mathcolor="red"> # </mstyle> \color{red}{\#} #
    F [ i , j , k ] = ( j + 1 ) ∗ F [ i − 1 , j + 1 , k − 1 ] + ( M − j + 1 − k ) ∗ F [ i − 1 , j − 1 , k ] F[i, j, k] = (j+1)*F[i-1, j+1,k-1] + (M-j+1-k)*F[i-1,j-1,k] F[i,j,k]=(j+1)∗F[i−1,j+1,k−1]+(M−j+1−k)∗F[i−1,j−1,k] .

  • 第 i i i 行放 2 2 2 个棋子, <mstyle mathcolor="red"> # </mstyle> \color{red}{\#} #
    F [ i , j , k ] = C M − j + 2 − k 2 F [ i − 1 , j − 2 , k ] + ( M − j − k + 1 ) ∗ j ∗ F [ i − 1 , j , k − 1 ] + C j + 2 2 F [ i , j + 2 , k − 2 ] F[i, j, k] = C_{M-j+2-k}^{2}F[i-1,j-2,k] + (M-j-k+1)*j*F[i-1,j,k-1] + C_{j+2}^2F[i,j+2,k-2] F[i,j,k]=CM−j+2−k2​F[i−1,j−2,k]+(M−j−k+1)∗j∗F[i−1,j,k−1]+Cj+22​F[i,j+2,k−2] .

  • 不放棋子, (这个容易忘记) .
    F [ i , j , k ] = F [ i − 1 , j , k ] F[i, j, k] = F[i-1, j, k] F[i,j,k]=F[i−1,j,k] .

最后答案即为 ∑ F [ N , i , j ] \sum F[N, i, j] ∑F[N,i,j] .

<mstyle mathcolor="red"> 实 现 部 分 </mstyle> \color{red}{实现部分} 实现部分

  • 初值 F [ 0 , 0 , 0 ] = 0 F[0, 0, 0] = 0 F[0,0,0]=0 .
  • 由于要用到的组合数 m m m 都等于 2 2 2, 于是直接计算即可 . 
#include<bits/stdc++.h>

const int mod = 9999973;
const int maxn = 105;

typedef long long LL;

int N, M;
int dp[maxn][maxn][maxn];

int C(int m){ return m*(m-1) >> 1; }

int main(){
        scanf("%d%d", &N, &M);
        dp[0][0][0] = 1;
        for(int i = 1; i <= N; i ++)
                for(int j = 0; j <= M; j ++)
                        for(int k = 0; k <= M; k ++){
                                dp[i][j][k] = dp[i-1][j][k];
                                if(k-1 >= 0) dp[i][j][k] = ((LL)dp[i][j][k] + dp[i-1][j+1][k-1] * (j+1)) % mod;
                                if(j-1 >= 0 && (M-(j-1)-k)) dp[i][j][k] = ((LL)dp[i][j][k] + (LL)dp[i-1][j-1][k] * (M-(j-1)-k) % mod) % mod;
                                if(j-2 >= 0 && (M-(j-2)-k)) dp[i][j][k] = ((LL)dp[i][j][k] + (LL)dp[i-1][j-2][k] * C(M-(j-2)-k) % mod) % mod;
                                if(k-1 >= 0 && (M-j-(k-1))) dp[i][j][k] = ((LL)dp[i][j][k] + (LL)(dp[i-1][j][k-1] * (M-j-(k-1)) % mod)* j % mod) % mod;
                                if(k-2 >= 0) dp[i][j][k] = ((LL)dp[i][j][k] + (LL)dp[i-1][j+2][k-2] * C(j+2) % mod) % mod;
                        }
        int Ans = 0;
        for(int j = 0; j <= M; j ++)
                for(int k = 0; k <= M; k ++)
                        Ans = ((LL)Ans + dp[N][j][k]) % mod;
        printf("%d", Ans);
        return 0;
}