题意
给定一个长度为 \(n\) 的数组 \(b\)，判断是否存在一个长度为 \(n\) 的数组 \(a\)，使得 \(b\) 中每一个元素都可以由 \(a\) 中两个位置不同的元素相加得到。若存在，输出任意一个 \(a\)。
\(2\le n\le 10^3,1\le b_i\le 10^6\)。
题解
简单分析，如果 \(b\) 中有两个元素相同则肯定可以，如果存在三个数 \(x,y,z\) 满足 \(x+y-z\) 是偶数则肯定可以。于是接下来只考虑所有数都是奇数的情况。
每个 \(a_i\) 对应一个点，\(b_i\) 对应一条边，则构成一个基环树。对于不在环上的部分，如果不是一条链，则将一个叶子接到另一个叶子下面，显然答案依然存在。于是形态变成了一个环接一条链。也就是一条链加一条连接一个端点的边。
设 \(a_1=x\)，则 \(a_2=b_1-x,a_3=b_2-b_1+x,a_4=b_3-b_2+b_1-x,\dots\)。注意此时 \(b\) 并非输入的顺序。此时仅 \(b_n\) 未满足。根据上述的分析，\(b_n\) 由 \(a_1\) 与一个 \(a_i\) 相加得到。由于所有 \(b\) 都是奇数，显然 \(i\) 需要为偶数。则问题转化为在 \(b\) 中找到两个长度相等，和相等的子序列。
由鸽巢原理，\(\binom{n}{n/2}>10^6\times\frac{n}{2}\) 时一定存在。所以 \(n>27\) 时在前 \(27\) 个中找即可。设 \(m=\min(n,27)\)，复杂度 \(O(m2^m)\)。