Atcoder Regular Contest++ 233 A.Strange Subset Sum

题目分析

本题为交互题。隐藏集合 $A \subseteq \{1, 2, \dots, N-1\}$，其大小为 $|A| = \lfloor N/2 \rfloor$。如果 $A$ 的某个子集元素和等于 $N$，称其为“特殊子集”。我们需要在最多 $\lfloor \frac{3N}{4} \rfloor$ 次询问内，确定是否存在特殊子集；若存在，求出特殊子集的最小大小。

---

核心数学结论：答案只能是 $2, 3$ 或 $-1$

1. 最小大小不可能为 $1$：
   因为集合中的所有元素都满足 $1 \le a \le N-1$，任何单个元素都不可能等于 $N$。

2. 最小大小不可能 $\ge 4$：
   定理：如果 $A$ 中存在元素和为 $N$ 的子集，且 $A$ 中不存在和为 $N$ 的二元组，那么 $A$ 中一定存在和为 $N$ 的三元组。

   简要证明：
   若 $A$ 中没有和为 $N$ 的二元组，则对于所有的互补对 $\{x, N-x\}$，它们在 $A$ 中的元素个数不能为 $2$。由鸽巢原理和元素总数守恒可知：每对互补对 $\{x, N-x\}$ 恰好有且仅有一个元素在 $A$ 中（若 $N$ 为偶数，则 $N/2 \in A$）。
   假设存在大小 $k \ge 4$ 的子集 $S = \{s_1 < s_2 < \dots < s_k\} \subseteq A$ 使得 $\sum s_i = N$。
   考虑两项之和 $u = s_i + s_j$：

   • 因为 $A$ 是一个“半集”，对于任何值 $u \in [1, N-1]$，必有 $u \in A$ 或 $N - u \in A$。
   • 若 $N - u \in A$ 且 $N - u \notin \{s_i, s_j\}$，则 $\{s_i, s_j, N - u\}$ 构成一个大小为 $3$ 的互异三元组，其和为 $N$；
   • 若不存在这样的三元组，通过考察最大项与其他项的组合，必能使得 $s_i + s_j \in A$，从而将这两项合并为一个新元素，归约出和为 $N$ 的大小为 $k-1$ 的子集。
   • 由有限降次法（Fermat’s Method of Descent），最终一定能归约到大小为 $3$ 的特殊子集。

   因此，特殊子集的最小大小只有三种可能：$2$、$3$ 或 $-1$。

---

交互策略（询问预算 $\le \lfloor \frac{3N}{4} \rfloor$）

我们将 $\{1, \dots, N-1\}$ 按互补对分组：$\{1, N-1\}, \{2, N-2\}, \dots, \{M, N-M\}$，其中 $M = \lfloor (N-1)/2 \rfloor$。

1. 若 $N$ 为偶数：

   • 首先询问 $N/2$：
     • 若 $N/2 \notin A$：剩余的 $N/2$ 个元素必须全部选自 $N/2 - 1$ 个互补对。由鸽巢原理，必然至少存在一对互补对的两数同时属于 $A$！此时其和为 $N$，答案必为 $2$，只需花费 $1$ 次询问即可立即输出答案并结束！
     • 若 $N/2 \in A$：$N/2$ 占用 $1$ 个名额，剩余 $N/2 - 1$ 个元素分布在 $M = N/2 - 1$ 个互补对中。

2. 配对与抽屉检验（无论是奇数还是偶数且 $N/2 \in A$）：

   • 此时剩余 $M$ 个元素恰好要从 $M$ 对互补对中选出。设包含 $2$ 个元素的对数为 $k_2$，包含 $0$ 个元素的对数为 $k_0$。
   • 由总数守恒，必有 $k_2 = k_0$。
     • 若 $k_2 > 0$，则存在二元组和为 $N$，答案为 $2$；
     • 若 $k_2 = 0$，则每对互补对恰好包含 $1$ 个元素，无二元组。
   • 我们先询问前一半元素 $1, 2, \dots, M$（共 $M \le \frac{N-1}{2}$ 次询问）：
     • 将在 $A$ 中的元素记入集合 $S_1$；不在 $A$ 中的记入集合 $S_0$。
     • 显然 $|S_1| + |S_0| = M$，故 $\min(|S_1|, |S_0|) \le \lfloor M/2 \rfloor \le N/4$。
   • 我们只需检验元素较少的那个集合：
     • 若 $|S_1| \le |S_0|$：对所有 $x \in S_1$，询问 $N - x$。若某个回答为 Yes，则找到了 $x, N-x \in A$，立即输出 ! 2；若全部为 No，则证明 $k_2 = 0$。
     • 若 $|S_0| < |S_1|$：对所有 $x \in S_0$，询问 $N - x$。若某个回答为 No，说明出现了包含 $0$ 个元素的对，即 $k_0 > 0 \implies k_2 > 0$，立即输出 ! 2；若全部为 Yes，则证明 $k_0 = 0 \implies k_2 = 0$。

   总询问次数统计：

   • 偶数时至多 $1 + M + \lfloor M/2 \rfloor = N/2 + \lfloor (N-2)/4 \rfloor \le \lfloor \frac{3N}{4} \rfloor$；
   • 奇数时至多 $M + \lfloor M/2 \rfloor \le \lfloor \frac{3N}{4} \rfloor$。
     完全严格满足题目限制！

---

离线判定三元组

当确认 $k_2 = 0$ 时，集合 $A$ 的每个元素均已完全确定（$x \in S_1 \iff x \in A, N-x \notin A$；$x \in S_0 \iff x \notin A, N-x \in A$）。
此时二元组不存在，我们只需离线检验 $A$ 中是否存在互异三元组 $x < y < z$ 满足 $x + y + z = N$：

• 根据初等对称多项式与牛顿恒等式：
  $$e_3 = \frac{1}{6} (s_1^3 - 3 s_1 s_2 + 2 s_3)$$
  其中 $s_1(x) = \sum_{a \in A} x^a, s_2(x) = \sum_{a \in A} x^{2a}, s_3(x) = \sum_{a \in A} x^{3a}$。
• 提取 $x^N$ 的系数：
  • $[x^N] s_1^3 = \sum_{c \in A} [x^{N-c}] (s_1^2)$：只需对 $s_1(x)$ 做一次多项式自卷积即可。
  • $[x^N] s_1 s_2 = \sum_{b \in A} [N - 2b \in A]$：$O(N)$ 遍历即可。
  • $[x^N] s_3 = [N \bmod 3 == 0 \text{ 且 } N/3 \in A]$：$O(1)$。
• 由于 $s_1^2$ 的每项系数表示两个 $A$ 中元素之和等于该下标的组数，其值最大不超过 $|A| \le 10^5 < 998244353$，因此直接在模 $998244353$ 下做一次 NTT 即可获得精确的非负整数结果，无需 CRT，总时间复杂度为 $O(N \log N)$。
• 若 $e_3 > 0$，输出 ! 3；否则输出 ! -1。

---

C++ 代码实现

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdlib>

using namespace std;

const int MOD = 998244353;
const int G = 3;

long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

long long modInverse(long long n) {
    return power(n, MOD - 2);
}

void ntt(vector<int>& a, bool invert) {
    int n = a.size();
    for (int i = 1, j = 0; i < n; i++) {
        int bit = n >> 1;
        for (; j & bit; bit >>= 1) j ^= bit;
        j ^= bit;
        if (i < j) swap(a[i], a[j]);
    }
    for (int len = 2; len <= n; len <<= 1) {
        long long wlen = power(G, (MOD - 1) / len);
        if (invert) wlen = modInverse(wlen);
        for (int i = 0; i < n; i += len) {
            long long w = 1;
            for (int j = 0; j < len / 2; j++) {
                long long u = a[i + j];
                long long v = (a[i + j + len / 2] * w) % MOD;
                a[i + j] = (u + v < MOD ? u + v : u + v - MOD);
                a[i + j + len / 2] = (u - v >= 0 ? u - v : u - v + MOD);
                w = (w * wlen) % MOD;
            }
        }
    }
    if (invert) {
        long long n_inv = modInverse(n);
        for (int i = 0; i < n; i++) {
            a[i] = (a[i] * n_inv) % MOD;
        }
    }
}

bool ask(int a) {
    cout << "? " << a << "\n";
    cout.flush();
    string resp;
    if (!(cin >> resp)) exit(0);
    if (resp == "-1") exit(0);
    return resp == "Yes";
}

void answer(int s) {
    cout << "! " << s << "\n";
    cout.flush();
}

void solve() {
    int N;
    if (!(cin >> N)) exit(0);

    int M = (N - 1) / 2;
    bool n_half_in_A = false;

    // 若 N 为偶数，先询问 N/2
    if (N % 2 == 0) {
        int half = N / 2;
        if (!ask(half)) {
            // N/2 不在 A 中，由鸽巢原理必存在二元组互补对
            answer(2);
            return;
        }
        n_half_in_A = true;
    }

    // 询问前一半元素 1..M
    vector<int> S1, S0;
    for (int x = 1; x <= M; x++) {
        if (ask(x)) S1.push_back(x);
        else S0.push_back(x);
    }

    // 检验较小的集合以确定是否存在和为 N 的二元组
    bool pair_found = false;
    if (S1.size() <= S0.size()) {
        for (int x : S1) {
            if (ask(N - x)) {
                pair_found = true;
                break;
            }
        }
    } else {
        for (int x : S0) {
            if (!ask(N - x)) {
                pair_found = true;
                break;
            }
        }
    }

    if (pair_found) {
        answer(2);
        return;
    }

    // 此时不存在和为 N 的二元对，重构 A 的全部元素
    vector<int> in_A(N, 0);
    vector<int> A_elements;
    if (n_half_in_A) {
        in_A[N / 2] = 1;
        A_elements.push_back(N / 2);
    }
    for (int x : S1) {
        in_A[x] = 1;
        A_elements.push_back(x);
    }
    for (int x : S0) {
        in_A[N - x] = 1;
        A_elements.push_back(N - x);
    }

    if (A_elements.size() < 3) {
        answer(-1);
        return;
    }

    // 使用 NTT 计算是否存在三元组
    int L = 1;
    while (L <= 2 * N) L <<= 1;
    vector<int> s1(L, 0);
    for (int x : A_elements) s1[x] = 1;

    vector<int> s1_sq = s1;
    ntt(s1_sq, false);
    for (int i = 0; i < L; i++) s1_sq[i] = (1LL * s1_sq[i] * s1_sq[i]) % MOD;
    ntt(s1_sq, true);

    long long term1 = 0;
    for (int c : A_elements) {
        if (N - c >= 0 && N - c < L) term1 += s1_sq[N - c];
    }
    long long term2 = 0;
    for (int b : A_elements) {
        if (N - 2 * b >= 0 && N - 2 * b < N && in_A[N - 2 * b]) term2++;
    }
    long long term3 = 0;
    if (N % 3 == 0 && in_A[N / 3]) term3 = 1;

    long long e3 = (term1 - 3 * term2 + 2 * term3) / 6;

    if (e3 > 0) {
        answer(3);
    } else {
        answer(-1);
    }
}

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