[ARC145D] Non Arithmetic Progression Set

james1BadCreeper · 2022-11-09 00:48:25 · 题解

upd: 感谢 \@Delov 的 Hack，现在已经更换为正确的构造方式，麻烦管理重审。

首先，y-x\neq z-y 相当于 x+z\neq 2y。

我们先抛开和为 M 的限制，考虑如何搞定最后那个不等的限制条件。
这里先给出结论：将数写成三进制，当数的所有位都是 0,1 时可以满足。
为什么呢？考虑 x+z=2y，y 乘上 2 之后每一位都是 0 或 2，而 x 和 z 必定有一位不一样（否则就相等了），加上之后肯定有一位是 1，必定不等于 2y。所以不等关系永远满足。

现在假定我们构造出来的集合可以表示为递增序列 a，然后进行下面对 M 的限制的讨论。

假设我们的 s 与 M 的差为 x，整个序列如果同时加上或减去一个数，其性质仍然满足。那么我们可以通过这一点将差 x 控制在 0\sim n-1 内。我们将三进制位的最后一位留白（即最后一位不进行构造，留出来一个 0），然后选择任意 x 个数加上 1 即可，最后一位的改变并不会影响答案。

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;
typedef long long i64;

int n, a[10005];
i64 m, s = 0;

int main(void) {
    cin >> n >> m;
    for (int p = 1; p <= n; ++p) {
        int x = 0, i = p * 2;
        for (int j = 0, z = 1; j < 16; ++j, z *= 3)
            if ((i >> j) & 1) x += z;
        a[p] = x; s += a[p];
    }
    int x = ((m - s) % n + n) % n;
    for (int i = 1; i <= x; ++i) ++a[i], ++s;
    i64 buf = (m - s) / n; s = 0;
    for (int i = 1; i <= n; ++i) printf("%d ", a[i] + buf);
    putchar('\n');
    return 0;
}