很不错的trick。
[ARC145D] Non Arithmetic Progression Set
先考虑 \(y-x \neq z-y\)。
如果往差去想的话就错了。有一个巧妙的技巧，先说结论：将数全部转成三进制，只要所有集合里所有数的三进制只有 \(0/1\) ，那么一定可以满足条件。
证明很简单，首先变形为 \(x+z = 2 \times y\) ，如果满足上面的构造，在三进制中，\(y\) 乘上 \(2\) 后每一位都是 \(0\) 或 \(2\) ，但是因为\(x \ne z\) ，\(x+y\) 一定有一位是 \(1\) ，那么两边一定不相等。
那么做法就很简洁了，我们构造出序列 \(a\) ，整个列同时加上一个数使得元素之和与 \(m\) 的差 \([0,n)\) 之间，最后对剩下的几个元素都加 \(1\) 就可以了（所以在构造的时候要让所以\(a_i\)的最低位为 \(0\) ）。
#include<bits/stdc++.h>
#define int long long
using namespace std;
#define endl '\n'
#define rep(i, l, r) for(int i = (l); i <= (r); ++ i)
#define per(i, r, l) for(int i = (r); i >= (l); -- i)
#define se second
#define fi first
#define pb push_back
#define pii pair<int, int>
const int N = 1e5 + 10;
int pw[20];
int a[N];
int n, m, sum;
void Jail() {cin >> n >> m;pw[0] = 1; rep(i, 1, 17) pw[i] = pw[i - 1] * 3;int s = (1 << 16) - 1; rep(i, 1, n) {while((s & 1) == 1) s --;rep(j, 0, 15) {if((s >> j) & 1) a[i] += pw[j];}sum += a[i];-- s;} int x = ((m - sum) % n + n) % n;rep(i, 1, x) a[i] ++, ++ sum;reverse(a + 1, a + n + 1);int t = (m - sum) / n;rep(i, 1, n) cout << a[i] + t << ' ';
}
signed main() {// freopen("a.in", "r", stdin);// freopen("a.out", "w", stdout); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);int T = 1;// cin >> T;while(T --) Jail();return 0;
}