D. Exam in MAC 详解

题目重述

给定一个严格递增的整数集合 $s$（$0 \le s_i \le c$）和一个整数 $c$。要求计算满足 $0 \le x \le y \le c$ 且 $x+y \notin s$ 且 $y-x \notin s$ 的整数对 $(x,y)$ 的数量。

思路分析

直接枚举所有 $(x,y)$ 不可行，因为 $c$ 可达 $10^9$。需要利用容斥原理，从总对数中减去不合法的对数，再加回被重复减去的部分。

1. 总对数

不考虑任何限制时，满足 $0 \le x \le y \le c$ 的对数为：

$$\text{total} = \sum_{x=0}^{c} (c - x + 1) = \frac{(c+1)(c+2)}{2} $$

2. 减去 $x+y \in s$ 的对数

对于固定的 $v \in s$，方程 $x+y = v$ 在 $0 \le x \le y \le c$ 下的解数：

• $x$ 的取值范围：$x$ 最小为 $\max(0, v-c)$，最大为 $\lfloor v/2 \rfloor$。
• 由于 $v \le c$，$v-c \le 0$，所以 $x$ 从 $0$ 到 $\lfloor v/2 \rfloor$。
• 解的数量为 $\lfloor v/2 \rfloor + 1$。

因此，所有 $x+y \in s$ 的对数为：

$$\text{sum\_add} = \sum_{v \in s} \left( \left\lfloor \frac{v}{2} \right\rfloor + 1 \right) $$

3. 减去 $y-x \in s$ 的对数

对于固定的 $d \in s$，方程 $y-x = d$ 在 $0 \le x \le y \le c$ 下的解数：

• $x$ 可以从 $0$ 到 $c-d$，$y = x+d$，自动满足 $x \le y$。
• 解的数量为 $c-d+1$。

因此，所有 $y-x \in s$ 的对数为：

$$\text{sum\_diff} = \sum_{d \in s} (c - d + 1)$$

4. 加回同时满足 $x+y \in s$ 且 $y-x \in s$ 的对数

同时满足两个条件的 $(x,y)$ 对应两个集合中的数 $v = x+y$ 和 $d = y-x$。解方程组：

$$\begin{cases} x+y = v \\ y-x = d \end{cases} \Longrightarrow x = \frac{v-d}{2},\quad y = \frac{v+d}{2} $$

要求 $x,y$ 为非负整数且 $x \le y$，这等价于：

• $v$ 和 $d$ 同奇偶（否则 $x,y$ 非整数）
• $v \ge d$（保证 $x \ge 0$）
• 自动满足 $y \le c$？因为 $v,d \le c$，所以 $v+d \le 2c$，即 $y \le c$ 恒成立。

因此，对于集合 $s$ 中的任意两个数 $v,d$（允许相等），若 $v \ge d$ 且 $v \equiv d \pmod{2}$，则唯一确定一个合法对 $(x,y)$。注意当 $v = d$ 时，$x=0,y=v$，也是合法的。

于是，同时满足条件的对数等于：将 $s$ 中的数按奇偶性分类，设偶数的个数为 $\text{even}$，奇数的个数为 $\text{odd}$。对于同一奇偶类中的数，任意选取两个（可相同）且第一个不小于第二个，这样的有序对数目为：

$$\frac{m(m+1)}{2}$$

其中 $m$ 为该类的大小。因此，加回的数量为：

$$\text{add\_back} = \frac{\text{even}(\text{even}+1)}{2} + \frac{\text{odd}(\text{odd}+1)}{2} $$

5. 最终答案

由容斥原理：

$$\text{ans} = \text{total} - \text{sum\_add} - \text{sum\_diff} + \text{add\_back} $$

算法步骤

1. 读入 $n, c$ 和数组 $s$。
2. 计算 $\text{total} = \frac{(c+1)(c+2)}{2}$（注意用 64 位整数）。
3. 初始化 $\text{even}=0,\text{odd}=0$。
4. 遍历每个 $s_i$：
   • $\text{sum\_add} \mathrel{+}= s_i/2 + 1$
   • $\text{sum\_diff} \mathrel{+}= c - s_i + 1$
   • 若 $s_i$ 为偶数则 $\text{even}++$，否则 $\text{odd}++$。
5. 计算 $\text{add\_back} = \frac{\text{even}(\text{even}+1)}{2} + \frac{\text{odd}(\text{odd}+1)}{2}$。
6. 输出 $\text{total} - \text{sum\_add} - \text{sum\_diff} + \text{add\_back}$。

时间复杂度 $O(n)$，空间复杂度 $O(1)$。

代码实现（含注释）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void solve() {
    int n, c;
    cin >> n >> c;
    vector<int> s(n);
    for (int i = 0; i < n; ++i) cin >> s[i];

    ll total = (ll)(c + 1) * (c + 2) / 2;   // 总对数
    ll sum_add = 0, sum_diff = 0;
    int even = 0, odd = 0;

    for (int v : s) {
        sum_add += v / 2 + 1;               // x+y = v 的对数
        sum_diff += c - v + 1;              // y-x = v 的对数
        if (v % 2 == 0) ++even;
        else ++odd;
    }

    ll add_back = (ll)even * (even + 1) / 2 + (ll)odd * (odd + 1) / 2;
    ll ans = total - sum_add - sum_diff + add_back;
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}

验证样例

以第一个测试用例为例：$n=3,c=3,s=\{1,2,3\}$。

• $\text{total} = \frac{4\times5}{2}=10$
• $\text{sum\_add} = (1/2+1)+(2/2+1)+(3/2+1)= (0+1)+(1+1)+(1+1)=1+2+2=5$
• $\text{sum\_diff} = (3-1+1)+(3-2+1)+(3-3+1)=3+2+1=6$
• $\text{even}=1\ (2),\ \text{odd}=2\ (1,3)$
• $\text{add\_back} = \frac{1\cdot2}{2}+\frac{2\cdot3}{2}=1+3=4$
• $\text{ans}=10-5-6+4=3$，与输出一致。

注意事项

• 使用 long long 避免溢出，因为 $c$ 可达 $10^9$，总对数约为 $5\times10^{17}$，需 64 位整数。
• 集合 $s$ 已保证严格递增，但算法不依赖该性质（只需元素值）。
• 奇偶分类的正确性源于 $x+y$ 与 $y-x$ 同奇偶。