2026牛客暑期多校 8——B-Deep Finesse（深算）

题目大意

深算

时间限制：C/C++/Rust/Pascal 2 秒，其他语言 4 秒
空间限制：C/C++/Rust/Pascal 1024 MB，其他语言 2048 MB

汐和风子正在一个庞大的数字世界里斗智：这个世界包含从 $1$ 到 $10^{100}$ 的所有整数。

对局开始前，汐要从这些整数中恰好挑选 $n$ 个互不相同的数作为自己的手牌，其余的所有数则全部归风子所有。

随后进行 $n$ 轮出牌。每一轮中：

• 风子先手，从她自己剩余的数中打出一个；

• 汐必须立刻从自己剩余的手牌中打出一个数作为回应。（她要出一个比风小的数）

危险的规则在于：若风子打出的数严格小于汐回应的数，风子当场获胜。只有当汐打出的数小于等于风子打出的数时，本轮才算安全通过，两个数随即被弃置，游戏继续进行。

汐要想取得胜利，必须撑过全部 $n$ 轮，始终不让风子打出更小的数。

更糟糕的是，游戏开始前风子还附加了一道限制：她指定了 $m$ 个特定的数，并宣布汐的初始手牌中必须包含这 $m$ 个数中的每一个。

于是汐开始盘算：在所有包含这 $m$ 个指定数、大小为 $n$ 的手牌方案中，有多少种能够保证她必胜——即无论风子如何巧妙地出牌，汐都有办法撑到最后？

答案可能极其巨大，请对 $998244353$ 取模后输出。

每个测试点包含多组测试数据。

第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试数据组数。

对于每组测试数据：

• 第一行包含两个整数 $n$ 和 $m$（$1 \le m \le n \le 5000$）；

• 第二行包含 $m$ 个整数 $a_1, a_2, \ldots, a_m$（$1 \le a_i \le 10^9$），表示汐必须包含在手牌中的特定数字。保证 $a$ 中没有重复元素。

保证所有测试数据的 $n$ 之和不超过 $5000$。

对于每组测试数据，输出一个整数，表示能够保证汐必胜的初始手牌方案数，对 $998244353$ 取模。

3
1 1
2
2 1
2
6 3
1 4 5

0
1
34

第一组数据：$n = 1$，且手牌必须包含 $2$，因此汐的手牌被唯一确定为 $\lbrace 2 \rbrace$。若风子打出 $1$，汐只能回应 $2$，此时 $1 < 2$，风子立即获胜。因此不存在必胜方案，答案为 $0$。

第二组数据：$n = 2$，手牌必须包含 $2$。可以验证，只有手牌为 $\lbrace 1, 2 \rbrace$ 时汐才能保证获胜，因此答案为 $1$。

第三组数据：$n = 6$，手牌必须包含 $1, 4, 5$ 这三个数，另外还需从剩余整数中选出 $3$ 个。在所有这样的手牌中，恰有 $34$ 种能保证汐必胜，因此答案为 $34$。

思路讲解

问：风子想最大化获胜概率，她会采取怎样的出牌策略？

答：风子为了尽可能让自己的牌小于汐的回应牌，一定会贪心地从小到大打出自己手中最小的 $n$ 张牌。因此，汐只需考虑如何战胜风子手中最小的 $n$ 个数即可。

问：为了抵挡风子打出的前 $n$ 小的牌，汐的手牌必须满足什么条件？

答：汐手牌中第 $k$ 小的牌必须小于等于风子手中第 $k$ 小的牌。这意味着，对于任意数字 $x$，在从 $1$ 到 $x$ 的区间内，汐持有的牌的数量必须大于等于风子持有的牌的数量。

问：汐的手牌最大可以是多少？

答：由于汐要在前 $2n$ 个数中获得比风子更多的牌（且两人最终各有 $n$ 张），汐的手牌必须全部包含在 $1$ 到 $2n$ 的范围内。如果有任何大于 $2n$ 的数，汐在前 $2n$ 中的牌数将小于 $n$，必然在最后一轮失败。

问：如何将这个条件转化为经典的组合计数模型并求解？（这个确实是一个非常经典的 dp 模型啊）

答：将考察 $1$ 到 $2n$ 的过程视作折线图：属于汐的牌计为向右上走一步（+1），属于风子的牌计为向右下走一步（-1）。合法方案等价于从 $(0,0)$ 走到 $(2n,0)$，中途不跌落 $x$ 轴以下，并且在指定的 $m$ 个位置必须向右上走。可以通过 $O(n^2)$ 动态规划求解。

问：为什么汐的必胜条件可以转化为卡特兰折线（括号序列）模型？

#include <iostream>
#include <vector>

using namespace std;

const int MOD = 998244353;

void solve() {
    int n;
    int m;
    cin >> n >> m;

    vector<int> a(m);
    bool possible = true;
    
    for (int i = 0; i < m; ++i) {
        cin >> a[i];
        // 如果汐被强制要求选大于 2n 的牌，则她在前 2n 里的牌数不足 n 张，必然无法挡住风子前 n 小的牌
        if (a[i] > 2 * n) {
            possible = false;
        }
    }

    if (!possible) {
        cout << 0 << "\n";
        return;
    }

    // 标记哪些数字是汐必须选的（即折线图中必须向右上走的位置）
    vector<bool> is_fixed(2 * n + 1, false);
    for (int i = 0; i < m; ++i) {
        is_fixed[a[i]] = true;
    }

    // dp[j] 表示当前前缀和（相对高度）为 j 的方案数
    vector<int> dp(n + 1, 0);
    dp[0] = 1;
    
    // next_dp 用于滚动数组更新
    vector<int> next_dp(n + 1, 0);

    for (int i = 1; i <= 2 * n; ++i) {
        // 每轮开始前初始化 next_dp 为 0
        for (int j = 0; j <= n; ++j) {
            next_dp[j] = 0;
        }

        if (is_fixed[i]) {
            // 当前数字必须属于汐，高度强制 +1
            for (int j = 1; j <= n; ++j) {
                next_dp[j] = dp[j - 1];
            }
        } else {
            // 当前数字既可以给汐，也可以给风子
            for (int j = 0; j <= n; ++j) {
                // 如果分配给汐，高度 +1
                if (j > 0) {
                    next_dp[j] = (next_dp[j] + dp[j - 1]) % MOD;
                }
                // 如果分配给风子，高度 -1，但前提是高度不能超过 n 且不跌破 0
                if (j < n) {
                    next_dp[j] = (next_dp[j] + dp[j + 1]) % MOD;
                }
            }
        }

        // 将本轮计算的结果滚动覆盖回 dp 数组
        for (int j = 0; j <= n; ++j) {
            dp[j] = next_dp[j];
        }
    }

    // 最终我们需要高度为 0，即汐和风子各拿到恰好 n 张牌
    cout << dp[0] << "\n";
}

int main() {
    // 优化输入输出流速度
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t;
    if (cin >> t) {
        while (t > 0) {
            solve();
            t--;
        }
    }
    
    return 0;
}

AC代码

AC

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=84449016

源代码（队友代码 ai 注释版）

/*
 * ============================================================================
 *  2026 牛客暑期多校训练营 8   B - Deep Finesse
 *  https://ac.nowcoder.com/acm/contest/133883/B
 * ============================================================================
 *
 *  【题意】
 *    数域是 [1, 10^100]。Ushio 先选 n 个互不相同的数作为手牌 S，
 *    剩下所有数都归 Fuuko（记为 F = [1,10^100] \ S）。
 *    共进行 n 轮：每轮 Fuuko 先出一个自己的数 x，Ushio 必须立刻用自己
 *    剩余的某个数 y 应对。若 x < y（Fuuko 的数严格更小）则 Fuuko 立刻获胜；
 *    只有 y <= x 时这一轮才安全通过，两个数一起弃掉。
 *    Ushio 要撑满 n 轮才算赢。
 *    额外限制：给定 m 个数 a[1..m]，Ushio 的手牌必须全部包含它们。
 *    问：满足限制的大小为 n 的手牌中，有多少个是「无论 Fuuko 怎么打都必胜」的，
 *    答案对 998244353 取模。
 *
 * ----------------------------------------------------------------------------
 *  【关键结论】把 S 排序为 s_1 < s_2 < ... < s_n，则
 *
 *          S 必胜  <==>  s_k <= 2k - 1   对每个 k = 1..n 都成立
 *
 *  【推导】
 *   (1) 转成匹配问题。
 *       Ushio 要撑满 n 轮，等价于：Fuuko 无论拿出哪 n 个数 T ⊆ F，
 *       都存在 T 到 S 的一个完美匹配，使得每个 t ∈ T 匹配到一个不同的
 *       s ∈ S 且 s <= t。
 *       （充分性：有匹配就照匹配出牌；必要性：Ushio 的实际出牌本身就是一个匹配。
 *         Ushio 的最优贪心是「出不超过 x 的最大的数」，把小牌留着更灵活。）
 *
 *   (2) Fuuko 的最劣策略显然是拿自己最小的 n 个数（数越小，能应对它的牌越少）。
 *       设 F 从小到大为 f_1 < f_2 < ...，由 Hall 定理，匹配存在
 *       <==> 对每个 k，|{s ∈ S : s <= f_k}| >= k
 *       <==> s_k <= f_k  （第 k 小对第 k 小）
 *
 *   (3) 把 f_k <= 某值 翻译成只跟 S 有关的条件。
 *       设 s_k = v。此时 [1, v-1] 中恰有 k-1 个 S 的元素，
 *       所以 [1, v-1] 中 Fuuko 的数有 (v-1) - (k-1) = v-k 个。
 *       条件 f_k >= v 等价于「小于 v 的 Fuuko 的数不足 k 个」，即
 *              v - k <= k - 1   <==>   v <= 2k - 1
 *       于是条件就是 s_k <= 2k-1。
 *
 *  【两条直接推论】
 *    - 手牌里所有数都 <= 2n-1（因为 s_n <= 2n-1），
 *      所以只需在值域 [1, 2n-1] 上考虑；给定的 a_i 只要有一个 > 2n-1 就直接输出 0。
 *    - 条件只在 v = 2k-1（奇数）处才是「新的」限制，偶数位置不产生新约束
 *      （v = 2k 时的条件 s_k <= 2k-1 已经在 v = 2k-1 处卡过了）。
 *
 * ----------------------------------------------------------------------------
 *  【做法】按值域从小到大扫描的计数 DP。
 *    从 v = 1 扫到 v = 2n-1，逐个决定「值 v 选不选进手牌」。
 *      dp[c] = 只考虑 [1, v] 这些值、已经选了 c 个数的方案数。
 *    转移：
 *      - 选 v：dp[c] -> next[c+1]
 *      - 不选 v：dp[c] -> next[c]，但若 v 是必选数（constraint[v] = true）则不允许
 *    剪枝（施加必胜条件）：
 *      扫完 v = 2k-1 之后，前缀 [1, 2k-1] 中必须已经选够 k 个数
 *      （否则 s_k > 2k-1，违反结论），所以把所有 c < k 的状态清零。
 *    答案 = dp[n]。
 *
 *  【复杂度】每组 O(n^2)，因为 sum(n) <= 5000，总复杂度 O((sum n)^2) 上界 2.5e7。
 * ============================================================================
 */

#include <bits/stdc++.h>
#include <bits/extc++.h>

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vii = vector<pii>;
using vll = vector<pll>;

#define endl '\n'
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define mem(a, b) memset(a, b, sizeof(a))
#define rep(i, a, n) for (int i = a; i < n; i++)
#define per(i, a, n) for (int i = n - 1; i >= a; i--)
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define clock cerr << "Time elapsed: " << (double)clock() / CLOCKS_PER_SEC << " s.\n"

const int MOD = 998244353;
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const ld EPS = 1e-9;
const ld PI = acos(-1);

// 快速幂（带模）：返回 a^b mod
template <typename T>
inline T qpow(T a, T b, T mod) {
    T res = 1;
    while (b) {
        if (b & 1) {
            res = res * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

// 快速幂（不带模）：返回 a^b
template <typename T>
inline T qpow(T a, T b) {
    T res = 1;
    while (b) {
        if (b & 1) {
            res = res * a;
        }
        a = a * a;
        b >>= 1;
    }
    return res;
}

void solve() {
    ll n, m;
    cin >> n >> m;

    vl a(m);

    // possible = false 表示存在无法满足的必选数，答案直接是 0
    bool possible = true;

    // constraint[v] = true 表示值 v 是「必须选入手牌」的数
    // 只需要开到 2n-1（下标 0 .. 2n-1），因为更大的值不可能出现在必胜手牌里
    vl constraint(2 * n, false);

    for (int i = 0; i < m; ++i) {
        cin >> a[i];
        if (a[i] > 2 * n - 1) {
            // 必胜条件要求 s_n <= 2n-1，即手牌中最大的数也不能超过 2n-1。
            // 现在被强制要选一个超过 2n-1 的数，必胜手牌不存在。
            // 注意：这里不能直接 return，必须把剩下的 m 个数读完，否则输入流会错位。
            possible = false;
        } else {
            constraint[a[i]] = true;
        }
    }

    if (!possible) {
        cout << 0 << "\n";
        return;
    }

    // dp[c]：当前已经扫描完某个值 v 的前缀 [1, v]，其中选了 c 个数进手牌的方案数
    // 初始时前缀为空 [1, 0]，只有「选了 0 个」这一种方案
    vl dp(n + 1, 0);
    dp[0] = 1;

    // 从小到大枚举值域中的每一个值 v，决定它选或不选
    for (int v = 1; v <= 2 * n - 1; ++v) {
        vl next(n + 1, 0);

        // need = true 表示 v 是必选数，不允许「不选」这条转移
        bool need = constraint[v];

        for (int c = 0; c <= n; ++c) {
            if (dp[c] == 0) {
                continue;  // 无效 / 已被剪枝的状态，跳过
            }

            // 转移 1：把 v 选进手牌，选中数量 +1（手牌总数不能超过 n）
            if (c + 1 <= n) {
                next[c + 1] = (next[c + 1] + dp[c]) % MOD;
            }

            // 转移 2：不选 v，选中数量不变。只有 v 不是必选数时才允许
            if (!need) {
                next[c] = (next[c] + dp[c]) % MOD;
            }
        }

        // 施加必胜条件：v 为奇数时，写 v = 2k-1，则 k = (v+1)/2。
        // 条件 s_k <= 2k-1 等价于「前缀 [1, 2k-1] 里至少已经选了 k 个数」，
        // 所以把所有 c < k 的状态判死（清零）。
        // v 为偶数时不产生新约束，无需处理。
        if (v % 2 == 1) {
            int k = (v + 1) / 2;
            for (int c = 0; c < k; ++c) {
                next[c] = 0;
            }
        }

        dp = move(next);
    }

    // 扫完整个值域 [1, 2n-1] 后恰好选满 n 个数的方案数，就是答案
    cout << dp[n] << "\n";
}

int main() {
    fastio;
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

心路历程（WA，TLE，MLE……）