第一次不看任何解析A出的省选难度题，留作纪念。

难度：省选/NOI-

题目描述

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

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

Sample input

1 3

Sample output

7

说明

【样例说明】
        除了3个格子里都塞满了炮以外，其它方案都是可行的，所以一共有2*2*2-1=7种方案。
【数据范围】
        100%的数据中N和M均不超过100
        50%的数据中N和M至少有一个数不超过8
        30%的数据中N和M均不超过6

题解

        考察动态规划，还是有一定难度的，但在省选题中算简单的了。这里的状态转移是性质转移。
        记dp(x，y，t)表示x行y列的棋盘在满足P(t)性质的条件下所有的方案数，P性质定义如下：

  • P(0)：第一行不能有棋子
  • P(1)：第一行仅有一个棋子
  • P(2)：第一行有两个棋子

        只有这三种情况，因为每一行一列不可能有三个及以上数目的棋子。
        对于t=0的情况很容易进行状态转移，这是因为首行没有棋子，不会对下面的棋子选取产生任何影响。

        t=1的情况就复杂很多。注意到第一行仅有且必须有一个棋子，它所在的一列的后x-1行可能有0个或1个棋子。可以最这两个子情况分别讨论，方案总数即是它们的和。当后x-1行没有棋子时，删去这一列和首行，得到一个x-1行y-1列的棋盘。这时发现首行的棋子对这个x-1行y-1列的棋盘棋子选取没有任何影响，方案总数即为dp(x-1，y-1，0)+dp(x-1，y-1，1)+dp(x-1，y-1，2)，再乘上y（被删去的一列有y种选法）就是第一个子情况的方案数。当后x-1行有一个棋子时，删去首行并将这一列拿到最左端，将这个棋盘（看作矩阵）转置，这是一个y行x-1列的棋盘且首行仅有一个棋子，故方案数即为dp(y，x-1，1)，再乘上y（理解同上）就是第二个子情况的方案数。于是有：

        最后再来看t=2的情况。仍然可以这种情况归结为三种子情况：两个棋子下面均没有其他棋子、一个棋子下面有一个棋子但另一个没有、两个棋子下面均有一个棋子。将它们三个的值加起来即可。第一种子情况理解与t=1相同，删去这两列，得到一个x-1行y-2列的棋盘，方案数为dp(x-1，y-2，0)+dp(x-1，y-2，1)+dp(x-1，y-2，2)，还需要乘上y*(y-1)/2（两个空列的组合数）。第二个子情况理解仍然同t=1时，删去没有棋子的那一列，将有一个棋子的一列拿到最左端，转置后得到一个y-1行x-1列的棋盘且满足P(1)性质，方案数即为dp(y-1，x-1，1)，需要再乘上y*(y-1)（乘一个排列数，将这两列作排列）。最后一种子情况很复杂，仍然需要划分为两种情况：下面的两个棋子不在同一行、下面的两个棋子在同一行。前者可以删去首行，再将两列合并，移到最左边，转置后得到一个y-1行x-1列并且满足性质P(2)的棋盘，方案数即为dp(y-1，x-1，2)，再乘上y*(y-1)即可。后者从棋盘中合并首行和两个棋子所在的一行，移到最顶端，这时下面的x-2行y列的棋盘在首行两个棋子所在的列不应有棋子，也就是两个空列。删去这两个空列，得到一个x-2行y-2列的棋盘，它的棋子选取没有受到影响，方案数为dp(x-2，y-2，0)+dp(x-2，y-2，1)+dp(x-2，y-2，2)，再乘上y*(y-1)/2（这里是一个组合数，是两个空列的选取情况），再乘上x-1（下面棋子所在行的情况）就是后一种情况的答案。
        因此t=2时的状态转移方程为：

        注意边界处理和取模，递推即可。答案即为dp(n，m，0)+dp(n，m，1)+dp(n，m，2)对9999973的模。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<iostream>
#include<cstring>

#define MAX 101
#define MOD 9999973
using namespace std;
long long dp[MAX][MAX][3] = {0};
int n, m;

long long DP(int x, int y, int t) {
    if (x == 0 || y == 0)return 0;
    if (x == 1) {
        if (t == 0)return 1;
        if (t == 1)return y;
        if (t == 2)return y * (y - 1) / 2;
    }
    if (y == 1) {
        if (t == 0)return (DP(x - 1, 1, 0) + DP(x - 1, 1, 1) + DP(x - 1, 1, 2)) % MOD;
        if (t == 1)return x;
        if (t == 2)return 0;
    }
    if (t == 2) {
        if (x == 2)return y * (y - 1) / 2 * (y * y + y + 2) / 2;
        if (y == 2)return x * x;
    }
    //上面是边界处理
    if (dp[x][y][t] >= 0)return dp[x][y][t];//记忆化
    //下面是状态转移，t=2时方程太长，分开计算
    if (t == 0)return dp[x][y][t] = (DP(x - 1, y, 0) + DP(x - 1, y, 1) + DP(x - 1, y, 2)) % MOD;
    if (t == 1)return dp[x][y][t] = ((DP(x - 1, y - 1, 0) + DP(x - 1, y - 1, 1) + DP(x - 1, y - 1, 2)) % MOD + DP(y, x - 1, 1)) * y % MOD;
    int ans = 0;
    ans += (DP(x - 1, y - 2, 0) + DP(x - 1, y - 2, 1) + DP(x - 1, y - 2, 2)) * y * (y - 1) / 2 % MOD;
    ans += DP(y - 1, x - 1, 1) * y * (y - 1) % MOD;
    ans %= MOD;
    ans += DP(y - 1, x - 1, 2) * y * (y - 1) % MOD + (DP(x - 2, y - 2, 0) + DP(x - 2, y - 2, 1) + DP(x - 2, y - 2, 2)) % MOD * y * (y - 1) / 2 * (x - 1) % MOD;
    return dp[x][y][t] = ans % MOD;
}

int main() {
    cin >> n >> m;
    memset(dp, -1, sizeof(dp));
    cout << (DP(n, m, 0) + DP(n, m, 1) + DP(n, m, 2)) % MOD << endl;
    return 0;
}

        虽然花了我3个小时去想它的解法（太弱），但评测用时36ms，内存占0.93mb AC这题还是值得的。