【DP】中国象棋

$Description$

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

$Input$

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

$Output$

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

$Sample$ $Input$

1 3

$Sample$ $Output$

7

$Hint$

除了在3个格子里都塞满炮以外，其他方案都是可行的。所以一共有 $2^3-1=7$ 种方案。
30% 的数据中 N 和 M 均不超过 6
50% 的数据中 N 和 M 至少有一个数不超过 8
100% 的数据中 N 和 M 不超过 100

$Train$ $of$ $Thought$

DP，不是状压DP
用 $F[i][j][k]$来表示在第 $i$行已经有 $j$列有一个棋子， $k$列有两个棋子
来看一下怎么转移
第一种情况，我们可以不放任何棋，则为 $F[i - 1][j][k]$
第二种就是只放一颗棋，又分两种情况，一种是放在那一列没有其他棋的情况下，就是 $F[i - 1][j - 1][k] * (m - j + 1 - k)$，另一种是放在这一列已经有一颗棋的情况，为 $F[i - 1][j + 1][k - 1] * (j + 1)$
第三种是放两颗棋，然后又分三种，一种同时放在两列都没棋， $F[i - 1][j - 2][k] * C^2_{(m - j + 2 - k)}$，另一种是同时放在两列都有1颗棋， $F[i - 1][j + 2][k - 2] * C^2_{(j + 2)}$，最后一种是一颗放有过一颗棋一列，另一颗放没放过棋的一列， $F[i - 1][j][k - 1] * j * (m - j - k + 1)$
整理一下：

一.不放棋
$F[i - 1][j][k]$

二.放一颗棋
1. $F[i - 1][j - 1][k] * (m - j + 1 - k)$
2. $F[i - 1][j + 1][k - 1] * (j + 1)$

三.放两颗棋
1. $F[i - 1][j - 2][k] * C^2_{(m - j + 2 - k)}$
2. $F[i - 1][j + 2][k - 2] * C^2_{(j + 2)}$
3. $F[i - 1][j][k - 1] * j * (m - j - k + 1)$

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define Mod 9999973
#define ll long long
using namespace std;ll F[105][105][105], A[105];
ll n, m, Ans;int main()
{scanf("%lld%lld", &n, &m);for(int i = 1; i <= m; ++i)A[i] = (i * (i - 1) / 2) % Mod;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(j >= 1)F[i][j][k] += F[i - 1][j - 1][k] * (m - j + 1 - k);if(k >= 1)F[i][j][k] += F[i - 1][j + 1][k - 1] * (j + 1);if(j >= 2)F[i][j][k] += F[i - 1][j - 2][k] * A[m - j + 2 - k];if(k >= 2)F[i][j][k] += F[i - 1][j + 2][k - 2] * A[j + 2];if(k >= 1)F[i][j][k] += F[i - 1][j][k - 1] * j * (m - j - k + 1);F[i][j][k] %= Mod;}for(int j = 0; j <= m; ++j)for(int k = 0; k <= m - j; ++k)Ans += F[n][j][k];printf("%lld", Ans % Mod);return 0;
}