专栏文章

AT ARC200D |A + A|

rrizynvu
AT_arc200_d题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio8khag
此快照首次捕获于
2025/12/02 15:07
3 个月前
此快照最后确认于
2025/12/02 15:07
3 个月前
查看原文
cnblogs。
首先让 aa 特殊一点，考虑到若让 aa 的元素都减掉一个值，那么和的数量是不变的，于是减掉 a1a_1，就可以强制要求 a1=0a_1 = 0。
接下来进行一些尝试，发现 0+1=1,1+1=2,1+2=3⋯0 + 1 = 1, 1 + 1 = 2, 1 + 2 = 3\cdots，于是构造 (0,1,⋯ ,x)(0, 1, \cdots, x)，0∼2x0\sim 2x 共 2x+12x + 1 个数就可以被凑出了。
那么 KK 为奇数就已经被解决了，此时只需要考虑偶数的情况了。
上面的构造看起来比较优美，于是考虑从这个基础上调整 O(1)\mathcal{O}(1) 个值来达成目标。
毕竟刚刚的选取都是正着选的，为什么不能倒着选呢？
考虑到 m−1≡−1(modm),m−2≡−2(modm)m - 1\equiv -1\pmod m, m - 2\equiv -2\pmod m，于是选上 m−ym - y 这些相当于是把 [0,x][0, x] 向左平移了 yy 位并加入了一个 2m−2y2m - 2y 的值。
如果选取 m−1m - 1 发现好像没什么用。
不过如果选取 m−2m - 2，会发现当 x≥1x\ge 1 时，[0,x][0, x] 平移后能够得到 m−2,m−1m - 2, m - 1 这 22 个值，且还会有 2m−4≡m−4(modm)2m - 4\equiv m - 4\pmod m 这个值，会发现这就实现了多 33 个数的操作，能够把奇数转为偶数了。
接下来就是去分析使用的条件了，经过一定的分讨，或者可以自己代入一些值模拟，会知道 6≤K<M6\le K < M 都是可行的，那么就只需要考虑剩下的边界情况了。
首先对于 K=MK = M 的情况，全选上肯定可行。
接下来考虑 K=2K = 2 的情况，我们可以说明一定只会选出来 22 个数：
  • 当选出 11 个数时，最多只有 11 种组合，必然凑不出 22 种，不合法。
  • 当选出 ≥3\ge 3 个数 (x,y,z,⋯ )(x, y, z, \cdots) 时，x+x,x+y,x+zx + x, x + y, x + z 必然不同，于是至少有 33 种和，不合法。
对于选出 22 个数 0,x0, x 的情况，就只能要求 2x≡0(modm)2x \equiv 0\pmod m，那就是当 m mod 2=0m\bmod 2 = 0 时取 x=m2x = \frac{m}{2}，否则无解。
根据刚刚的经验，可以知道对于 K=4K = 4 时只可能选出 3/43 / 4 个数，尝试分讨：
  • 当选出 33 个数 0,x,y0, x, y 时，0,x,y0, x, y 本身不同，所以 2x,2y,x+y2x, 2y, x + y 中需要有 22 个值与 0,x,y0, x, y 中的某个值相等，考虑继续分讨：
    • 2x≡y,2y≡x2x \equiv y, 2y \equiv x，当 m mod 3=0m\bmod 3 = 0 时可以令 x=m3,y=2m3x = \frac{m}{3}, y = \frac{2m}{3}，此时 x+y≡0x + y \equiv 0 不合法。
    • 2x≡0,2y≡x2x\equiv 0, 2y\equiv x，当 m mod 4=0m\bmod 4 = 0 时可以令 x=m2,y=m4x = \frac{m}{2}, y = \frac{m}{4}（y=3m4y = \frac{3m}{4} 也可以），此时 x+y≡3m4x + y \equiv \frac{3m}{4} 合法。
    • x+y≡0x + y\equiv 0（等式右边不能为 x/yx / y，因为这会导出 x≡yx\equiv y），若 2x≡02x\equiv 0 会导出 x≡yx \equiv y，若 2x≡y2x\equiv y 会导出与第一次分讨相同的结果。
  • 当选出 44 个数 0,x,y,z0, x, y, z 时，0,x,y,z0, x, y, z 本身不同，所以 2x,2y,2z2x, 2y, 2z 都必须和 0,x,y,z0, x, y, z 中的某个值相等，于是分讨：
    • 2x≡y,2y≡z,2z≡x2x \equiv y, 2y\equiv z, 2z\equiv x，当 m mod 7=0m\bmod 7 = 0 时可以令 x=m7,y=2m7,z=4m7x = \frac{m}{7}, y = \frac{2m}{7}, z = \frac{4m}{7}，x+y≡3m7x + y\equiv \frac{3m}{7} 不合法。
    • 2x≡0,2y≡z,2z≡y2x\equiv 0, 2y\equiv z, 2z\equiv y，当 m mod 6=0m\bmod 6 = 0 时有 x=3m6,y=2m6,z=4m6x = \frac{3m}{6}, y = \frac{2m}{6}, z = \frac{4m}{6} 的值，x+y≡5m6x + y\equiv \frac{5m}{6} 不合法。
    • 2x≡0,2y≡x,2z≡y2x\equiv 0, 2y\equiv x, 2z\equiv y 或 2z≡x2z\equiv x，此时已经满足 m mod 4=0m\bmod 4 = 0，故不继续讨论（能发现 (0,m4,m2,3m4)(0, \frac{m}{4}, \frac{m}{2}, \frac{3m}{4}) 也是一组合法解）。
经过刚刚的分讨，可以知道只有当 m mod 4=0m\bmod 4 = 0 时满足条件，其中构造为 (0,m2,m4)(0, \frac{m}{2}, \frac{m}{4})。
时间复杂度 O(m)\mathcal{O}(m)。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...