2026 杭电暑期多校 8-1009-价值总是越大越好

题目大意

价值总是越大越好

时间限制：2000 ms (Java) / 1000 ms (其他)　　空间限制：524288 KB

给定一个长度为 $2N$ 的数组 $P$。数组中的非零元素互不相同，取值范围为 $1$ 到 $2N$；缺失的元素用 $0$ 表示。

你需要把所有的 $0$ 替换为尚未出现过的整数，使得最终的 $P$ 恰好是 $1$ 到 $2N$ 的一个排列。

定义一个排列的价值为

$$|P_1-P_2|+|P_3-P_4|+\cdots+|P_{2N-1}-P_{2N}|$$

请求出有多少种补全方式能使该价值取到最大值。答案对 $998244353$ 取模。

两种补全方式只要存在至少一个位置上的数不同，就视为不同的方式。

第一行输入一个整数 $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$。

对于每组测试数据输出一行，表示使排列价值最大的补全方式数量对 $998244353$ 取模后的结果。

3
4
3 0 0 5 6 8 0 4
2
0 0 0 0
3
4 6 1 5 3 2

2
16
1

第一组数据： 已出现的数为 $\{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}$

#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代码

源代码

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