[ARC145] Non Arithmetic Progression Set

Problem Statement

Construct a set $S$ of integers satisfying all of the conditions below. It can be proved that at least one such set $S$ exists under the Constraints of this problem.

• $S$ has exactly $N$ elements.
• The element of $S$ are distinct integers between $-10^7$ and $10^7$ (inclusive).
• $ displaystyle sum _{s in S} s = M$.
• $ y-xneq z-y$ for every triple $ x,y,z$ $(x < y < z)$ of distinct elements in $ S$.

$N$ $M$

$s_1$ $s_2$ $ldots$ $s_N$

3 9

1 2 6

5 -15

-15 -5 0 2 3

移一下项，得到 (2y=z+x)

考虑一个数的三进制。如果集合中所有数的三进制表示下只有 (0) 和(1)，那么 (2y) 的三进制表示下只由 (0) 和 (2) 组成。若要选出 (x+z=2y) ，当且仅当 (x=z=y)，而集合有不可重性。所以如果这样构造，可以得出答案。易得构造出的数在 ([-10^7,10^7]) 内（见附注）。

但是我们要保证所有数和为m。容易发现，如果一个集合 (s) 是合法的，那么给 (s) 中每一个数同时加上一个数，集合仍然没有等差数列。所以如果构造出序列后，我们先想办法让他们的和与 (m) 模 (n) 同余，然后再给每个数加上 (frac{(m-sum(s))}{n})即可。如何微调集合使得他们的和模 (n) 同余呢？在枚举三进制时，我们可以空出最后一位，然后微调。

上面就是大概思路，我们用样例详解

(n=5,m=-15)

首先构造有5个数的合法集合

((0010)_3=3)
((0100)_3=9)
((0110)_3=12)
((1000)_3=27)
((1010)_3=30)

和为 (3+9+12+27+30=81)，模 (5) 余 (1)。(m) 模 (5) 余 (0)。

所以我们要选择 (4) 个数加 (1)。集合变成了：

((0011)_3=4)
((0101)_3=10)
((0111)_3=13)
((1001)_3=28)
((1010)_3=30)

那么我们再给每个数减去 ((85-(-15))/5=20)。集合就是
$ {-16,-10,-7,8,10}$

代码就很好写了。

建议枚举初始合法三进制时用二进制枚举。

#include<bits/stdc++.h>
const int N=10005;
int n,s[N],ret;
long long m,x,sum,d;
int main()
{
	scanf("%d%lld",&n,&m);
	for(int i=2;i<=2*n;i+=2)
	{
		ret=3;
		for(int j=1;j<15;j++)
		{
			if(i>>j&1)
				s[i>>1]+=ret;
			ret*=3;
		}
		sum+=s[i>>1];
	}
	x=((m-sum)%n+n)%n;
	d=floor((1.00*m-sum)/n);
	for(int i=1;i<=x;i++)
		s[i]++;
	for(int i=1;i<=n;i++)
		printf("%lld ",s[i]+d);
}