题目地址：洛谷：【P2051】[AHOI2009]中国象棋 – 洛谷、BZOJ：Problem 1801. — [Ahoi2009]chess 中国象棋

题目描述

这次小可可想解决的难题和中国象棋有关，在一个N行M列的棋盘上，让你放若干个炮（可以是0个），使得没有一个炮可以攻击到另一个炮，请问有多少种放置方法。大家肯定很清楚，在中国象棋中炮的行走方式是：一个炮攻击到另一个炮，当且仅当它们在同一行或同一列中，且它们之间恰好 有一个棋子。你也来和小可可一起锻炼一下思维吧！

输入输出格式

输入格式：
一行包含两个整数N，M，之间由一个空格隔开。

输出格式：
总共的方案数，由于该值可能很大，只需给出方案数模9999973的结果。

输入输出样例

输入样例#1：

1 3

输出样例#1：

7

说明

样例说明
除了3个格子里都塞满了炮以外，其它方案都是可行的，所以一共有222-1=7种方案。

数据范围
100%的数据中N和M均不超过100
50%的数据中N和M至少有一个数不超过8
30%的数据中N和M均不超过6

题解

这道题在状态设计出来以后就没什么了。显然每行每列的炮不能超过2个，用dp[i][j][k]表示正在排第i行，有j列有1个炮，有k列有2个炮的状态。下面是若干转移方程。
①这一次不填炮
dp[i][j][k] += dp[i-1][j][k]
②这一次填1个炮，填在没炮的列，乘法原理选择一列
dp[i][j+1][k] += dp[i-1][j][k] * (m - j - k)
③这一次填1个炮，填在本来有1个炮的列，乘法原理选择一列
dp[i][j-1][k+1] += dp[i-1][j][k] * j
④这一次填2个炮，都填在没有填过的列，组合选择2列
dp[i][j+2][k] += dp[i-1][j][k] * C_{m-j-k}^2
⑤这一次填2个炮，分别填在没填过和有1个炮的列，乘法原理分别选择
dp[i][j][k+1] += dp[i-1][j][k] * (m - j - k) * j
⑥这一次填2个炮，都填在有1个炮的列，组合选择2列
dp[i][j+2][k] += dp[i-1][j][k] * C_j^2
这些写全了再对填完n列的各种情况加和即可。最后滚动数组优化下空间。

代码

注：这个式子比较长建议复制出去看或者看上面的式子。

// Code by KSkun, 2018/2
#include <cstdio>
#include <cstring>
typedef long long LL;

const int MO = 9999973;

int n, m;
LL dp[2][105][105], ans = 0;

inline LL cal(LL x) {
    return x * (x - 1) / 2;
}

inline int g(int x) {
    return x & 1;
} 

int main() {
    scanf("%d%d", &n, &m);
    dp[0][0][0] = 1;
    for(int i = 1; i <= n; i++) { // i行 
        for(int j = 0; j <= m; j++) { // 枚举1棋列 
            for(int k = 0; j + k <= m; k++) { // 枚举2棋列 
                if(dp[g(i - 1)][j][k]) {
                    //noif
                        dp[g(i)][j][k] = (dp[g(i)][j][k] + dp[g(i - 1)][j][k]) % MO; // 不放 
                    if(m - j - k > 0) 
                        dp[g(i)][j + 1][k] = (dp[g(i)][j + 1][k] + dp[g(i - 1)][j][k] * (m - j - k)) % MO; // 放1 0棋
                    if(j > 0) 
                        dp[g(i)][j - 1][k + 1] = (dp[g(i)][j - 1][k + 1] + dp[g(i - 1)][j][k] * j) % MO; // 放1 1棋
                    if(m - j - k > 1) 
                        dp[g(i)][j + 2][k] = (dp[g(i)][j + 2][k] + dp[g(i - 1)][j][k] * cal(m - j - k)) % MO; // 放2 0|0
                    if(m - j - k > 0 && j > 0) 
                        dp[g(i)][j][k + 1] = (dp[g(i)][j][k + 1] + dp[g(i - 1)][j][k] * (m - j - k) * j) % MO; // 放2 1|0
                    if(j > 1) 
                        dp[g(i)][j - 2][k + 2] = (dp[g(i)][j - 2][k + 2] + dp[g(i - 1)][j][k] * cal(j)) % MO; // 放2 1|1 
                }
            }
        }
        memset(dp[g(i + 1)], 0, sizeof dp[g(i + 1)]);
    }
    for(int i = 0; i <= m; i++) {
        for(int j = 0; i + j <= m; j++) {
            ans = (ans + dp[g(n)][i][j]) % MO;
        }
    }
    printf("%lld", ans);
    return 0;
}