2026 杭电暑期多校 8-1009-价值总是越大越好 · znzryb
# 题目大意
### 价值总是越大越好
时间限制:2000 ms (Java) / 1000 ms (其他) 空间限制:524288 KB
<!-- Notion block type: heading_4 -->
给定一个长度为 $2N$ 的数组 $P$。数组中的非零元素互不相同,取值范围为 $1$ 到 $2N$;缺失的元素用 $0$ 表示。
你需要把所有的 $0$ 替换为尚未出现过的整数,使得最终的 $P$ 恰好是 $1$ 到 $2N$ 的一个排列。
定义一个排列的价值为
$$
|P_1-P_2|+|P_3-P_4|+\cdots+|P_{2N-1}-P_{2N}|
$$
请求出有多少种补全方式能使该价值取到最大值。答案对 $998244353$ 取模。
两种补全方式只要存在至少一个位置上的数不同,就视为不同的方式。
<!-- Notion block type: heading_4 -->
第一行输入一个整数 $T$,表示测试数据组数。
每组测试数据包含两行:
- 第一行输入一个整数 $N$,表示数组长度为 $2N$;
- 第二行输入 $2N$ 个整数 $P_1,P_2,\dots,P_{2N}$,其中 $0$ 表示该位置尚未填入数字。
对于每组测试数据,保证:
- $1\le N\le 2\times 10^5$;
- $0\le P_i\le 2N$;
- 所有非零的 $P_i$ 互不相同。
OJ 中只有一个正式测试点,该测试点满足:$T=10000$,$\sum N=10^6$。
<!-- Notion block type: heading_4 -->
对于每组测试数据输出一行,表示使排列价值最大的补全方式数量对 $998244353$ 取模后的结果。
<!-- Notion block type: heading_4 -->
```
3
4
3 0 0 5 6 8 0 4
2
0 0 0 0
3
4 6 1 5 3 2
```
<!-- Notion block type: heading_4 -->
```
2
16
1
```
<!-- Notion block type: heading_4 -->
**第一组数据:** 已出现的数为 $\{3,4,5,6,8\}$,需要把 $1,2,7$ 填入第 $2,3,7$ 个位置。枚举全部 $6$ 种填法,可得到的价值分别为 $10,8,10,8,12,12$,最大价值为 $12$,共有 $2$ 种方式达到:
- $[3,7,1,5,6,8,2,4]$,价值为 $|3-7|+|1-5|+|6-8|+|2-4|=4+4+2+2=12$;
- $[3,7,2,5,6,8,1,4]$,价值为 $|3-7|+|2-5|+|6-8|+|1-4|=4+3+2+3=12$。
**第二组数据:** 所有位置均为空,需要用 $1,2,3,4$ 填满,共 $24$ 种排列。其中最大价值为 $4$,例如 $[1,4,2,3]$ 的价值为 $3+1=4$,$[3,1,2,4]$ 的价值为 $2+2=4$;而如 $[1,2,3,4]$ 的价值仅为 $1+1=2$。统计后恰有 $16$ 种排列的价值等于 $4$。
**第三组数据:** 数组中没有 $0$,本身已经是一个排列,因此只存在唯一一种"补全方式"(即不作任何改动),答案为 $1$。
# 思路讲解

我们的目标是想让这个和最大,所以说我们不想要浪费我们所有能够控制的集合,就是U,我们肯定**想让U中大的数字去减小的数字**。
数组中共有三种数对:
1. **两个数字都已知**(类型 1):它们之间谁大谁小已经固定,因此它们的 $+1$ 和 $-1$ 符号也已经固定,我们无法改变。
2. **一个已知,一个缺失(为** $0$**)**(类型 2):假设**已知的数字构成集合** $F_2$。
3. **两个数字都缺失(均为** $0$**)**(类型 3):设有 $c_3$ 对这样的数对。
**令缺失的数字集合为** $M$。我们能自由分配符号的**数字集合恰好为** $U = F_2 \cup M$。**集合** $U$ **的大小为** $2(c_2 + c_3)$。
为了使得价值最大,我们将集合 $U$ 中的数字排序,将**较大的一半**分配符号 $+1$,将**较小的一半**分配符号 $-1$。由于 $U$ 中的数字各不相同,较大的一半中的任意数字都严格大于较小一半中的任意数字,因此这种最优的符号分配是**绝对合法且唯一**的。
现在问题转化为,在保证集合 $U$ 最优符号分配的前提下,有多少种合法的填数(配对)方式:
• 设集合 $M$ 中被分配为 $+1$ 的数字个数为 $m_+$。
• 设集合 $M$ 中被分配为 $-1$ 的数字个数为 $m_-$。
• 每一个“双 $0$”的数对(类型 3)需要消耗一个 $M$ 中的 $+1$ 和一个 $M$ 中的 $-1$。这两个数字在这两个 $0$ 的位置上有两种排列方式,因此 $c_3$ 个这样的数对会产生 $2^{c_3}$ 种内部排列。
• 确定了所有符号位置后,$m_+$ 个 $+1$ 数字可以任意填入需要 $+1$ 的空位,共有 $m_+!$ 种填法;同理,$m_-$ 个 $-1$ 数字共有 $m_-!$ 种填法。
因此最大价值的补全方式数量即为:$\displaystyle 2^{c_3} \times m_+! \times m_-! \pmod{998244353}$

```cpp
#include <iostream>
#include <vector>
using namespace std;
// 定义题目要求的取模常数
const int MOD = 998244353;
// 预处理阶乘数组,以便在 O(1) 时间内获取 m_+! 和 m_-!
// N 最大为 2*10^5,所以最大阶乘需要计算到 200000
const int MAX_N = 200005;
long long fact[MAX_N];
// 预计算阶乘函数
void precompute() {
fact[0] = 1;
for (int i = 1; i < MAX_N; ++i) {
fact[i] = (fact[i - 1] * i) % MOD;
}
}
void solve() {
int n;
cin >> n;
// 数组长度为 2N
int total_len = 2 * n;
vector<int> p(total_len);
// present[i] 标记数字 i 是否已经在数组中出现过
vector<bool> present(total_len + 1, false);
for (int i = 0; i < total_len; ++i) {
cin >> p[i];
if (p[i] != 0) {
present[p[i]] = true;
}
}
// 1. 收集缺失的数字集合 M (Missing elements)
vector<int> missing_elements;
for (int i = 1; i <= total_len; ++i) {
if (!present[i]) {
missing_elements.push_back(i);
}
}
// 2. 统计两种特殊情况:
// double_zero_pairs 对应理论中的 c3:表示两个数字都缺失的数对数量 (0, 0)
int double_zero_pairs = 0;
// in_F2[i] 标记数字 i 是否属于集合 F2
// F2 是指:在 (已知的非零数字, 0) 这种包含且仅包含一个 0 的数对中,那个已知的数字
vector<bool> in_F2(total_len + 1, false);
for (int i = 0; i < n; ++i) {
int a = p[2 * i];
int b = p[2 * i + 1];
if (a == 0 && b == 0) {
double_zero_pairs++;
} else if (a == 0 && b != 0) {
in_F2[b] = true;
} else if (a != 0 && b == 0) {
in_F2[a] = true;
}
}
// 3. 构造可以自由分配符号的集合 U = F2 U M
vector<int> free_elements;
for (int i = 1; i <= total_len; ++i) {
// 如果一个数字是缺失的 (M) 或者属于与 0 配对的已知数字 (F2),就加入集合 U
if (!present[i] || in_F2[i]) {
free_elements.push_back(i);
}
}
// 4. 找到中位数阈值,划分大数(+1)和小数(-1)
// 因为 free_elements 是按 1 到 2N 的顺序扫描生成的,所以天生就是从小到大排好序的
int half = free_elements.size() / 2;
// 如果没有空位需要填补(或者说没有 0),直接输出 1 种方式(原样)
if (half == 0) {
cout << 1 << "\n";
return;
}
// threshold 为大数集合的最小值,所有 >= threshold 的数字将被分配符号 +1,小于的分配 -1
int threshold = free_elements[half];
// 5. 将缺失的数字集合 M 划分为需要充当大数的 m_plus 和需要充当小数的 m_minus
int missing_plus = 0; // 理论中的 m_+
int missing_minus = 0; // 理论中的 m_-
for (int x : missing_elements) {
if (x >= threshold) {
missing_plus++;
} else {
missing_minus++;
}
}
// 6. 计算最终的排列组合方案数: 2^(c3) * (m_+)! * (m_-)!
long long ans = 1;
// 乘上 2 的 c3 次方 (每一个 (0,0) 对内部有两种数字排列方式)
for (int i = 0; i < double_zero_pairs; ++i) {
ans = (ans * 2) % MOD;
}
// 乘上大数的任意填入排列数 (m_+)!
ans = (ans * fact[missing_plus]) % MOD;
// 乘上小数的任意填入排列数 (m_-)!
ans = (ans * fact[missing_minus]) % MOD;
// 输出最终答案
cout << ans << "\n";
}
int main() {
// 优化输入输出流速度,防止大数据超时
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// 程序开始前先预计算阶乘
precompute();
int t;
if (cin >> t) {
while (t--) {
solve();
}
}
return 0;
}
```
# AC代码
::: 源代码
```cpp
```
:::
# 心路历程(WA,TLE,MLE……)