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-x\neq z-y$ for every triple $ x,y,z$ $(x < y < z)$ of distinct elements in $ S$.
Constraints
- $1 \leq N \leq 10^4$
- $|M| \leq N\times 10^6$
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$N$ $M$
Output
Let $s_1,s_2,\ldots,s_N$ be the elements of $S$. Print a set $S$ that satisfies the conditions in the following format:
$s_1$ $s_2$ $\ldots$ $s_N$
If multiple solutions exist, any of them will be accepted.
Sample Input 1
3 9
Sample Output 1
1 2 6
We have $2-1 \neq 6-2$ and $1+2+6=9$, so this output satisfies the conditions. Many other solutions exist.
Sample Input 2
5 -15
Sample Output 2
-15 -5 0 2 3
$M$ may be negative.
移一下项，得到 \(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);
}