这是一道比较优秀的方案数 DP 题。乍一看以为是状压 DP，然后发现数据范围过大所以只能重新思考（也就是看题解）。我们可以写出状态格式：
\[dp[ln][opit][tpit]，其中 ln 为行号，opit 代表第 ln 行内一个棋子的列数，tpit 代表第 ln 行内两个棋子的列数。\]
然后我们就可以根据不同情况来进行转移了。我们来看下面几组代码，其中每组都会有对应方程的意义。我们记\(dp[ln+1]\)为当前行号。首先，我们先要判定转移源的方案数不为\(0\)，之后再进行转移。
// 不放置棋子的情况; // Situation without placing; dp[ln + 1][opit][tpit] = (dp[ln + 1][opit][tpit] + dp[ln][opit][tpit]) % MOD;
// 在不放置棋子的位置上放置一个棋子;
// Situation of placing one on empty lines;
if (M - opit - tpit >= 1)
dp[ln + 1][opit + 1][tpit] = (dp[ln + 1][opit + 1][tpit] + dp[ln][opit][tpit] * (M - opit - tpit)) % MOD;
// 在放置了一个棋子的位置上放置一个棋子；
// Situation of placing one on lines with only piece;
if (opit >= 1)
dp[ln + 1][opit - 1][tpit + 1] = (dp[ln + 1][opit - 1][tpit + 1] + dp[ln][opit][tpit] * opit) % MOD;
// 在两个没有放置棋子的位置上放置两个棋子，其中 C2(num) = C^num_2;
// Situation of placing two pieces on the two empty slots;
if (M - opit - tpit >= 2)
dp[ln + 1][opit + 2][tpit] = (dp[ln + 1][opit + 2][tpit] + dp[ln][opit][tpit] * C2(M - opit - tpit)) % MOD;
// 在一个没有棋子的位置和一个有一个棋子的位置放置共两个棋子;
// Situation of placing one on the empty and another on the only slot;
if (M - opit - tpit >= 1 && opit >= 1)
dp[ln + 1][opit][tpit + 1] = (dp[ln + 1][opit][tpit + 1] + dp[ln][opit][tpit] * (M - opit - tpit) * opit) % MOD;
// 在两个一个棋子的位置放置共两个棋子;
// Situation of placing two on two only slots;
if (opit >= 2)
dp[ln + 1][opit - 2][tpit + 2] = (dp[ln + 1][opit - 2][tpit + 2] + dp[ln][opit][tpit] * C2(opit)) % MOD;
完整源码：
// P2051.cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#define ll long long
using namespace std;
const int MX_N = 102, MOD = 9999973;
ll dp[MX_N][MX_N][MX_N], N, M;
ll C2(ll num)
{
return (num * (num - 1)) / 2;
}
int main()
{
scanf("%lld%lld", &N, &M);
dp[0][0][0] = 1;
for (int ln = 0; ln < N; ln++)
for (int opit = 0; opit <= M; opit++)
for (int tpit = 0; tpit + opit <= M; tpit++)
if (dp[ln][opit][tpit])
{
// 不放置棋子的情况;
// Situation without placing;
dp[ln + 1][opit][tpit] = (dp[ln + 1][opit][tpit] + dp[ln][opit][tpit]) % MOD;
// 在不放置棋子的位置上放置一个棋子;
// Situation of placing one on empty lines;
if (M - opit - tpit >= 1)
dp[ln + 1][opit + 1][tpit] = (dp[ln + 1][opit + 1][tpit] + dp[ln][opit][tpit] * (M - opit - tpit)) % MOD;
// 在放置了一个棋子的位置上放置一个棋子；
// Situation of placing one on lines with only piece;
if (opit >= 1)
dp[ln + 1][opit - 1][tpit + 1] = (dp[ln + 1][opit - 1][tpit + 1] + dp[ln][opit][tpit] * opit) % MOD;
// 在两个没有放置棋子的位置上放置两个棋子，其中 C2(num) = C^num_2;
// Situation of placing two pieces on the two empty slots;
if (M - opit - tpit >= 2)
dp[ln + 1][opit + 2][tpit] = (dp[ln + 1][opit + 2][tpit] + dp[ln][opit][tpit] * C2(M - opit - tpit)) % MOD;
// 在一个没有棋子的位置和一个有一个棋子的位置放置共两个棋子;
// Situation of placing one on the empty and another on the only slot;
if (M - opit - tpit >= 1 && opit >= 1)
dp[ln + 1][opit][tpit + 1] = (dp[ln + 1][opit][tpit + 1] + dp[ln][opit][tpit] * (M - opit - tpit) * opit) % MOD;
// 在两个一个棋子的位置放置共两个棋子;
// Situation of placing two on two only slots;
if (opit >= 2)
dp[ln + 1][opit - 2][tpit + 2] = (dp[ln + 1][opit - 2][tpit + 2] + dp[ln][opit][tpit] * C2(opit)) % MOD;
}
ll ans = 0;
for (int i = 0; i <= M; i++)
for (int j = 0; i + j <= M; j++)
ans = (ans + dp[N][i][j]) % MOD;
printf("%lld\n", ans);
return 0;
}