Loading [MathJax]/extensions/tex2jax.js

P2051:「AHOI2009」中国象棋题解

这是一道比较优秀的方案数 DP 题。乍一看以为是状压 DP,然后发现数据范围过大所以只能重新思考(也就是看题解)。我们可以写出状态格式:

\[dp[ln][opit][tpit],其中 ln 为行号,opit 代表第 ln 行内一个棋子的列数,tpit 代表第 ln 行内两个棋子的列数。\]

然后我们就可以根据不同情况来进行转移了。我们来看下面几组代码,其中每组都会有对应方程的意义。我们记\(dp[ln+1]\)为当前行号。首先,我们先要判定转移源的方案数不为\(0\),之后再进行转移。

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
// 不放置棋子的情况;
// Situation without placing;
dp[ln + 1][opit][tpit] = (dp[ln + 1][opit][tpit] + dp[ln][opit][tpit]) % MOD;
// 不放置棋子的情况; // Situation without placing; dp[ln + 1][opit][tpit] = (dp[ln + 1][opit][tpit] + dp[ln][opit][tpit]) % MOD;
// 不放置棋子的情况;
// Situation without placing;
dp[ln + 1][opit][tpit] = (dp[ln + 1][opit][tpit] + dp[ln][opit][tpit]) % MOD;
Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
// 在不放置棋子的位置上放置一个棋子;
// 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 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 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;
Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
// 在放置了一个棋子的位置上放置一个棋子;
// 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;
// 在放置了一个棋子的位置上放置一个棋子; // 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;
// 在放置了一个棋子的位置上放置一个棋子;
// 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;
Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
// 在两个没有放置棋子的位置上放置两个棋子,其中 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;
// 在两个没有放置棋子的位置上放置两个棋子,其中 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;
// 在两个没有放置棋子的位置上放置两个棋子,其中 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;
Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
// 在一个没有棋子的位置和一个有一个棋子的位置放置共两个棋子;
// 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 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 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;
Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
// 在两个一个棋子的位置放置共两个棋子;
// 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;
// 在两个一个棋子的位置放置共两个棋子; // 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;
// 在两个一个棋子的位置放置共两个棋子;
// 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;

完整源码:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
// 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;
}
// 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; }
// 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;
}

 

Leave a Reply

Your email address will not be published. Required fields are marked *