这是一道比较优秀的方案数 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;
}

思路

这道题是一道比较典型的dp求方案数。这是我第一次做dp方案数的题目，这篇题解就作为我dp方案数专题的第一篇文章吧。

首先思考本题的dp方程时，需要用方案数dp的方式去思考。方案数是叠加的，所以每次转移时的运算就是相加而不是取最大最小值。这样的话，我们可以来真正的来思考本题方程。首先方程中需要有点的位置，亦需要小a和uim的状态。我们如何把魔液这个元素考虑进来呢？我们增加一个维度，来记录俩人魔液罐子的差值（当然，为负数的时候我们就可以加一个k进行取模运算，保证在正数范围内可以访问）。所以，dp[i][j][h][0/1]可以表示为走到(i,j)时两人魔罐插值为h时的方案数量，其中0代表小a走，1代表uim走。所以方程如下：

F[i][j][h][0] = (F[i][j][h][0] + F[i – 1][j][(h – map[i][j] + k) % k][1]) % P;
F[i][j][h][0] = (F[i][j][h][0] + F[i][j – 1][(h – map[i][j] + k) % k][1]) % P;
F[i][j][h][1] = (F[i][j][h][1] + F[i – 1][j][(h + map[i][j]) % k][0]) % P;
F[i][j][h][1] = (F[i][j][h][1] + F[i][j – 1][(h + map[i][j]) % k][0]) % P;

代码如下：

// P1373.cpp
#include <iostream>

using namespace std;
// Variables;
const int maxn = 802;
const int INF = 0x7fffffff;
const int P = 1000000007;
int n, m, k;
int map[maxn][maxn];
int F[maxn][maxn][20][2];
// Start to dp;
void dp()
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            for (int h = 0; h <= k; h++)
            {
                F[i][j][h][0] = (F[i][j][h][0] + F[i - 1][j][(h - map[i][j] + k) % k][1]) % P;
                F[i][j][h][0] = (F[i][j][h][0] + F[i][j - 1][(h - map[i][j] + k) % k][1]) % P;
                F[i][j][h][1] = (F[i][j][h][1] + F[i - 1][j][(h + map[i][j]) % k][0]) % P;
                F[i][j][h][1] = (F[i][j][h][1] + F[i][j - 1][(h + map[i][j]) % k][0]) % P;
            }
}

int main()
{
    // Input;
    cin >> n >> m >> k, ++k;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            // Initialize;
            cin >> map[i][j], F[i][j][map[i][j]][0] = 1;
    dp();
    long long ans = 0;
    // Calculate the answer;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            ans += F[i][j][0][1], ans %= P;
    // Output;
    cout << ans;
    return 0;
}

P2051:「AHOI2009」中国象棋题解

P1373:小a和uim之大逃离题解

思路