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

Auspiciousness

https://ac.nowcoder.com/acm/contest/57357/B

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

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

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

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

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

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

\begin{cases} \displaystyle f_{0,x,y,k} \leftarrow \sum_{i=1}^{k}f_{0,x+1,y,i}+\sum_{i=0}^{y+1}f_{1,x,y+1,i}\\ \displaystyle f_{1,x,y,k} \leftarrow \sum_{i=k+1}^{x+1}f_{1,x+1,y,i}+\sum_{i=0}^{y+1}f_{0,x,y+1,i}\\ \end{cases}

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

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

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

#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;
}

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

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

全站热榜