AT ARC200D |A + A|

rizynvu · 2025-08-19 21:53:59 · 题解

cnblogs。

首先让 a 特殊一点，考虑到若让 a 的元素都减掉一个值，那么和的数量是不变的，于是减掉 a_1，就可以强制要求 a_1 = 0。

接下来进行一些尝试，发现 0 + 1 = 1, 1 + 1 = 2, 1 + 2 = 3\cdots，于是构造 (0, 1, \cdots, x)，0\sim 2x 共 2x + 1 个数就可以被凑出了。

那么 K 为奇数就已经被解决了，此时只需要考虑偶数的情况了。

上面的构造看起来比较优美，于是考虑从这个基础上调整 \mathcal{O}(1) 个值来达成目标。

毕竟刚刚的选取都是正着选的，为什么不能倒着选呢？
考虑到 m - 1\equiv -1\pmod m, m - 2\equiv -2\pmod m，于是选上 m - y 这些相当于是把 [0, x] 向左平移了 y 位并加入了一个 2m - 2y 的值。

如果选取 m - 1 发现好像没什么用。
不过如果选取 m - 2，会发现当 x\ge 1 时，[0, x] 平移后能够得到 m - 2, m - 1 这 2 个值，且还会有 2m - 4\equiv m - 4\pmod m 这个值，会发现这就实现了多 3 个数的操作，能够把奇数转为偶数了。

接下来就是去分析使用的条件了，经过一定的分讨，或者可以自己代入一些值模拟，会知道 6\le K < M 都是可行的，那么就只需要考虑剩下的边界情况了。

首先对于 K = M 的情况，全选上肯定可行。

接下来考虑 K = 2 的情况，我们可以说明一定只会选出来 2 个数：

• 当选出 1 个数时，最多只有 1 种组合，必然凑不出 2 种，不合法。
• 当选出 \ge 3 个数 (x, y, z, \cdots) 时，x + x, x + y, x + z 必然不同，于是至少有 3 种和，不合法。

对于选出 2 个数 0, x 的情况，就只能要求 2x \equiv 0\pmod m，那就是当 m\bmod 2 = 0 时取 x = \frac{m}{2}，否则无解。

根据刚刚的经验，可以知道对于 K = 4 时只可能选出 3 / 4 个数，尝试分讨：

• 当选出 3 个数 0, x, y 时，0, x, y 本身不同，所以 2x, 2y, x + y 中需要有 2 个值与 0, x, y 中的某个值相等，考虑继续分讨：
• 当选出 4 个数 0, x, y, z 时，0, x, y, z 本身不同，所以 2x, 2y, 2z 都必须和 0, x, y, z 中的某个值相等，于是分讨：

经过刚刚的分讨，可以知道只有当 m\bmod 4 = 0 时满足条件，其中构造为 (0, \frac{m}{2}, \frac{m}{4})。

时间复杂度 \mathcal{O}(m)。

#include <bits/stdc++.h>

inline void solve() {
    int m, k;
    scanf("%d%d", &m, &k);

    std::vector<int> ans;

    if (k % 2 == 1) {
        for (int i = 0; i <= (k - 1) / 2; i++) ans.push_back(i);
    } else if (k == m) {
        for (int i = 0; i < m; i++) ans.push_back(i);
    } else if (k == 2) {
        if (m % 2 != 0) {
            return puts("No"), void();
        } else {
            ans = {0, m / 2};
        }
    } else if (k >= 6) {
        for (int i = 0; i <= (k - 4) / 2; i++) ans.push_back(i);
        ans.push_back(m - 2);
    } else if (m % 4 == 0) {
        ans = {0, m / 2, m / 4};
    } else {
        return puts("No"), void();
    }

    puts("Yes");
    printf("%zu\n", ans.size());
    for (int x : ans) printf("%d ", x);
    puts("");
}

int main() {
    int t; scanf("%d", &t);
    while (t--) solve();
    return 0;
}