2026牛客暑期多校 8——B-Deep Finesse(深算) · znzryb
## 题目大意
### 深算
时间限制:C/C++/Rust/Pascal 2 秒,其他语言 4 秒
空间限制:C/C++/Rust/Pascal 1024 MB,其他语言 2048 MB
<!-- Notion block type: heading_4 -->
汐和风子正在一个庞大的数字世界里斗智:这个世界包含从 $1$ 到 $10^{100}$ 的所有整数。
对局开始前,汐要从这些整数中恰好挑选 $n$ 个**互不相同**的数作为自己的手牌,其余的所有数则全部归风子所有。
随后进行 $n$ 轮出牌。每一轮中:
- **风子先手**,从她自己剩余的数中打出一个;
- 汐必须立刻从自己剩余的手牌中打出一个数作为回应。(她要出一个比风小的数)
危险的规则在于:若风子打出的数**严格小于**汐回应的数,风子当场获胜。只有当汐打出的数**小于等于**风子打出的数时,本轮才算安全通过,两个数随即被弃置,游戏继续进行。
汐要想取得胜利,必须撑过全部 $n$ 轮,始终不让风子打出更小的数。
更糟糕的是,游戏开始前风子还附加了一道限制:她指定了 $m$ 个特定的数,**并宣布汐的初始手牌中必须包含这** $m$ **个数中的每一个**。
于是汐开始盘算:在所有包含这 $m$ 个指定数、大小为 $n$ 的手牌方案中,有多少种能够保证她必胜——即无论风子如何巧妙地出牌,汐都有办法撑到最后?
答案可能极其巨大,请对 $998244353$ 取模后输出。
<!-- Notion block type: heading_4 -->
每个测试点包含多组测试数据。
第一行包含一个整数 $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$。
<!-- Notion block type: heading_4 -->
对于每组测试数据,输出一个整数,表示能够保证汐必胜的初始手牌方案数,对 $998244353$ 取模。
<!-- Notion block type: heading_4 -->
<!-- Notion block type: heading_4 -->
```
3
1 1
2
2 1
2
6 3
1 4 5
```
<!-- Notion block type: heading_4 -->
```
0
1
34
```
<!-- Notion block type: heading_4 -->
**第一组数据**:$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)$ 动态规划求解。
问:为什么汐的必胜条件可以转化为卡特兰折线(括号序列)模型?
```cpp
#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](https://ac.nowcoder.com/acm/contest/view-submission?submissionId=84449016)
::: 源代码(队友代码 ai 注释版)
```cpp
/*
* ============================================================================
* 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……)