题解 | 2023 年牛客多校第三场 B 题 Auspiciousness

题意：给定 $nn$ 表示有一个由 $\{1,2,3,\cdots ,2n\}\backslash \{1,2,3,\backslash cdots,2n\backslash \}$ 构成的 $2n2n$ 张牌的初始牌堆，同时自己这里有一个空的牌堆。执行以下的操作：

1. 翻开牌堆顶的一张牌，并放在自己牌堆的堆顶。
2. 记自己牌堆堆顶的一张牌大小为 $xx$。如果初始牌堆为空，结束。否则执行 $33$ 操作。
3. 若 $x\le nx\; \backslash le\; n$，则猜测初始牌堆翻出的下一张牌 $yy$ 比 $xx$ 大，否则猜测翻出来的下一张牌比 $xx$ 小。这时翻开初始牌堆的堆顶，并将这一张牌放在自己的牌堆的堆顶。如果猜测正确，则跳转到 $22$ 操作，否则结束游戏。

问对于 $(2n)!(2n)!$ 种牌的排列，总的抽取牌数有多少，对特定数字 $mm$ 取模。多测，$\sum n\le 300\backslash sum\; n\; \backslash le\; 300$，$1\le m\le 10^{9}1\backslash le\; m\; \backslash le\; 10^9$。

解法：首先不考虑空间复杂度，定义 $f_{i,x,y,k}f\_\{i,x,y,k\}$ 表示当前在抽取第 $2n-x-y+12n-x-y+1$ 张牌时，小于等于 $nn$ 的牌张数还剩 $xx$ 张，大于 $nn$ 的牌数还剩 $yy$ 张，在抽第 $2n-x-y2n-x-y$ 张（上一轮）牌时（1）如果是小于等于 $nn$ 的牌，则选了这小于等于 $nn$ 的剩下来的 $xx$ 张牌里面第 $kk$ 小的牌；（2）如果是大于 $nn$ 的牌，则选了这大于 $nn$ 的剩下来的 $yy$ 张牌里面第 $kk$ 小的牌；（该状态用 $i\in \{0,1\}i\; \backslash in\; \backslash \{0,1\backslash \}$ 区分）作为的现有方案总数（不考察后续初始牌堆的牌顺序）。

这样构造方案的思路：首先比较容易想到的是，维护大于 $nn$ 和小于等于 $nn$ 的个数，然后维护一个状态表示上一次是抽到大于的还是小于等于的。但是这样在枚举当前轮的时候，就无法避免重复选择的问题。因而修正到去掉已经选过的之后排多少，这样操作就不会导致重复问题，并且也方便刻画当前的大小。

既然不考虑重复问题，那么可以写出下面的转移方程：

对于答案统计，可以考虑对每一步成功抽牌进行分步统计——即不再统计有多少种抽牌方式能抽到 $ii$ 张牌，而是在能抽到第 $ii$ 张牌的状态中，每次叠加它的次数（贡献）。

不难发现状态数有 $O(n^3)O(n^3)$ 个，对于单个状态的计算如果按照上式直接计算，会达到 $O(n^4)O(n^4)$ 的复杂度。不难注意到第四个维度可以前缀和，因而可以使用前缀和优化掉第四维，得到下面一个未经过空间优化的代码（会 MLE）。

注意下面的代码中，为了统一 dp 方程形式，在 $[1,n][1,n]$ 部分是维护的第 $kk$ 大，在 $[n+1,2n][n+1,2n]$ 部分维护的是第 $kk$ 小。

#include <bits/stdc++.h>
using namespace std;
#define int long long
int dp[2][310][310][310];
int solve()
{
    int n, mod;
    cin >> n >> mod;
    // A：阶乘 C：组合数
    vector<int> fac(n * 2 + 3);
    vector<vector<int>> C(n * 2 + 3, vector<int>(n * 2 + 3));
    C[0][0] = fac[0] = 1;
    for (int i = 1; i <= n * 2; i++)
    {
        fac[i] = fac[i - 1] * i % mod;
        C[i][0] = 1;
        for (int j = 1; j <= i; j++)
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
    }
    // 清空
    for (int i = 0; i <= n + 3; i++)
        for (int j = 0; j <= n + 3; j++)
            for (int k = 0; k <= n + 3; k++)
                dp[0][i][j][k] = dp[1][i][j][k] = 0;
    // 快速取模
    function<void(int &, int)> add = [&](int &x, int y)
    {
        if ((x += y) >= mod)
            x -= mod;
    };
    function<void(int &, int)> del = [&](int &x, int y)
    {
        if ((x -= y) < 0)
            x += mod;
    };
    // 任何情况，都能拿走一张牌
    int ans = fac[2 * n];
    // 初始条件：在还没开始抽牌之前，大（[n+1,2n]）还剩n张，小（[1,n]）也剩n张。
    for (int i = 1; i <= n; i++)
    {
        dp[0][n][n][i] = i % mod; // 一开始是小，当前选择的牌是[1,i]范围，有i种
        dp[1][n][n][i] = i % mod; // 一开始是大，同理
    }
    // 枚举大小两类牌在本轮抽取完成后，各剩多少（x,y），倒序枚举
    for (int x = n; x >= 0; x--)
    {
        for (int y = n; y >= 0; y--)
        {
            if (x + y >= 2 * n) // 初值设定过
                continue;
            // 本次抽的是[1,n]中的牌
            for (int k = 1; k <= x; k++) 
            {
                if (x != n) // 上一轮抽到一张范围在[1,n]的牌，如果要继续游戏，如果当前抽到k，则上一轮抽出来的牌必须在[1,k]的范围（比当前小）
                    add(dp[0][x][y][k], (dp[0][x + 1][y][x + 1] - dp[0][x + 1][y][k] + mod) % mod);
                if (y != n) // 再枚举当前抽到的是一张大的，这时一定可以接着抽
                    add(dp[0][x][y][k], dp[1][x][y + 1][y + 1]);
                // 能走到当前这一步的状态，都统计一下这一次抽牌对答案的贡献
                add(ans, dp[0][x][y][k] * fac[x + y - 1] % mod);
            }
            // 前缀和一下
            for (int k = 1; k <= x; k++)
                add(dp[0][x][y][k], dp[0][x][y][k - 1]);
            // 本次抽到的是[n+1,2n]中的牌
            for (int k = 1; k <= y; k++)
            {
                if (y != n) // 上一轮抽到一张范围在[n+1,2n]的牌，如果要继续游戏，如果当前抽到k，则上一轮抽出来的牌必须在[k+1,y+1]的范围（比当前大）
                    add(dp[1][x][y][k], (dp[1][x][y + 1][y + 1] - dp[1][x][y + 1][k] + mod) % mod);
                if (x != n) // 上一轮抽到一张[1,n]的牌，都可以继续抽牌
                    add(dp[1][x][y][k], dp[0][x + 1][y][x + 1]);
                // 能走到当前这一步的状态，都统计一下这一次抽牌对答案的贡献
                add(ans, dp[1][x][y][k] * fac[x + y - 1] % mod);
            }
            // 前缀和一下
            for (int k = 1; k <= y; k++)
                add(dp[1][x][y][k], dp[1][x][y][k - 1]);
        }
    }
    // 全部能抽完的部分多算了一步
    add(ans, (fac[2 * n] - dp[0][1][0][1] - dp[1][0][1][1] + mod) % mod);
    return ans;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--)
        cout << solve() << "\n";
    return 0;
}

由于每次 $xx$ 只会从 $x+1x+1$ 转移，因而可以考虑再滚动掉最外层的一维数组（即 $xx$），即使用 $0,10,1$ 两个状态来表示当前的 $xx$ 和 $x+1x+1$。

#include <bits/stdc++.h>
using namespace std;
long long dp[2][2][310][310];
void Solve()
{
    int n, mod;
    scanf("%d%d", &n, &mod);
    vector<long long> fac(n * 2 + 3);
    vector<vector<long long>> C(n * 2 + 3, vector<long long>(n * 2 + 3));
    C[0][0] = fac[0] = 1;
    for (int i = 1; i <= n * 2; i++)
    {
        fac[i] = fac[i - 1] * i % mod;
        C[i][0] = 1;
        for (int j = 1; j <= i; j++)
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
    }
    for (int i = 0; i <= 1; i++)
        for (int j = 0; j <= n + 3; j++)
            for (int k = 0; k <= n + 3; k++)
                dp[0][i][j][k] = dp[1][i][j][k] = 0;
    // 快速取模
    function<void(long long &, long long)> add = [&](long long &x, long long y)
    {
        x += y;
        if (x >= mod)
            x -= mod;
    };
    function<void(long long &, long long)> del = [&](long long &x, long long y)
    {
        x -= y;
        if (x < 0)
            x += mod;
    };
    
    long long ans = fac[2 * n];
    // 在下面的代码中，为方便编写，因而考虑用(n-x)的奇偶性来作为滚动数组的标识
    // 初始条件
    for (int i = 1; i <= n; i++)
    {
        dp[0][0][n][i] = i % mod;
        dp[1][0][n][i] = i % mod;
    }
    int op = 0; // 滚动后x的代表
    // 枚举两个各剩多少
    for (int x = n; x >= 0; x--) 
    {
        for (int y = n; y >= 0; y--)
        {
            if (x + y == 2 * n || x + y == 0)
                continue;
           	// 第一类转移
            for (int k = 1; k <= x; k++)
            {
                if (x != n)
                    add(dp[0][op][y][k], (dp[0][op ^ 1][y][x + 1] - dp[0][op ^ 1][y][k] + mod) % mod);
                if (y != n)
                    add(dp[0][op][y][k], dp[1][op][y + 1][y + 1]);
                add(ans, dp[0][op][y][k] * fac[x + y - 1] % mod);
            }
            for (int k = 1; k <= x; k++)
                add(dp[0][op][y][k], dp[0][op][y][k - 1]);
            // 第二类转移
            for (int k = 1; k <= y; k++)
            {
                if (y != n)
                    add(dp[1][op][y][k], (dp[1][op][y + 1][y + 1] - dp[1][op][y + 1][k] + mod) % mod);
                if (x != n)
                    add(dp[1][op][y][k], dp[0][op ^ 1][y][x + 1]);
                add(ans, dp[1][op][y][k] * fac[x + y - 1] % mod);
            }
            for (long long k = 1; k <= y; k++)
                add(dp[1][op][y][k], dp[1][op][y][k - 1]);
        }
        op ^= 1;
        for (long long i = 0; i <= n + 3; i++)
            for (long long j = 0; j <= n + 3; j++)
                dp[0][op][i][j] = dp[1][op][i][j] = 0;
    }
    // 去掉抽走2n张牌的重复贡献
    add(ans, (fac[2 * n] - dp[1][op ^ 1][1][1] * 2 + mod * 2) % mod);
    printf("%lld\n", ans);
}
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
        Solve();
    return 0;
}