标签：10 cf1599j 元素 solution 偶数 cdots 集合 cases

CF1599J Solution

link

题意：

给你一个长为 \(n\) 的序列 \(b\)，请你构造一个长为 \(n\) 的序列 \(a\)，满足 \(b\) 中的数都能由 \(a\) 中两个不同下标的数相加得到。

无解报告 NO，\(n\le 10^3,b_i\le10^6\)。

---

我们发现如果我们能用 \(a_1\sim a_m\) 来凑出 \(b_1\sim b_m\)，剩下的令 \(a_i=b_i-a_{i-1}\) 即可满足条件。

考虑 \(m=3\) 的情况。假设

\[\begin{cases} a_1+a_2=b_1\\ a_2+a_3=b_2\\ a_3+a_1=b_3\\ \end{cases}\]

解得

\[\begin{cases} a_1=\dfrac{-b_1+b_2+b_3}{2}\\\\ a_2=\dfrac{b_1-b_2+b_3}{2}\\\\ a_3=\dfrac{b_1+b_2-b_3}{2}\\ \end{cases}\]

有整数解当且仅当 \(b_1+b_2+b_3\) 为偶数。

也就是说，只要 \(b\) 中存在至少一个偶数，我们把它挑出来拉上另外两个奇数或者两个偶数解上述方程，再令剩下的 \(a_i=b_i-a_{i-1}\) 即可满足条件。

那么如果 \(b\) 中只有奇数呢？

这个时候我们考虑 \(m\) 为偶数的情况。

\[\begin{cases} a_1+a_2=b_1\\ a_2+a_3=b_2\\ a_3+a_4=b_3\\ \cdots\\ a_{m-1}+a_m=b_{m-1}\\ a_m+a_1=b_m\\ \end{cases}\]

你发现这个方程组竟然不是线性无关的，就是说用前 \(m\) 条方程本可以推出

\[a_m+a_1=b_1+b_3+\cdots+b_{m-1}-b_2-b_4-\cdots-b_{m-2} \]

这个方程组要么无解，要么有无数组解（当且仅当 \(b_1+b_3+\cdots+b_{m-1}-b_2-b_4-\cdots-b_{m-2}=b_m\)）。

也就是说偶数项的 \(b\) 和等于奇数项的 \(b\) 和。

那么我们只需要找到 \(b\) 中的两个不相交的，大小相同的集合 \(S,T\) 满足 \(S\) 的元素和等于 \(T\) 的元素和即可。

一旦找到，我们随便代个 \(a_1\) 进去解出 \(a_1\sim a_m\)，令剩下的 \(a_i=b_i-a_{i-1}\) 即可。

想想看怎么找到 \(S\) 和 \(T\)。由于值域只有 \(10^6\)，直觉告诉我们一般情况下都是有解的。

考虑两个大小为 \(k\) 的集合，它们的各自的元素和 \(\le k\times 10^6\)，而把 \(2k\) 个元素分为这两个集合的方案数是 \(\binom{2k}k\)。

当 \(\binom{2k}k>k\times 10^6\) 时，根据抽屉原理，必定能找到两个集合的元素和相等。

我们再把这两个集合的公共部分去除就得到想要的 \(S\) 和 \(T\) 了。

摁摁计算器发现 \(\binom{28}{14}=40116600>14\times 10^6\)，也就是说 \(n\ge 28\) 时必定有解。

下面我们按照 \(n\gets \min(n,28)\) 来求方案。

考虑暴力搜索，先搜索前 \(\frac n 2\) 个数枚举每个数在 \(S\) 中，在 \(T\) 中或是不在任何集合中。

把搜到的 \(S,T\) 的大小差和元素和的差塞进哈希表里。再同理搜剩下的数，搜完后在哈希表找即可。

运行次数 \(\sim3^{14}\)，常数巨大。

标签：10,cf1599j,元素,solution,偶数,cdots,集合,cases
From： https://www.cnblogs.com/iorit/p/18040126