很牛阿。
\(n = 20\) 纯唐。
\(n = 500\)，我们每次选 \(6\) 个元素有 \(\binom{500}{6} = 2 \times 10^{13}\) 种方案，子集的和的最大值不超过 \(6 \times 10^{12}\)，根据鸽巢原理，显然有解。
怎么构造方案呢？我们考虑直接随机就过了。为什么？首先假设子集和是在 \([6, 6 \times 10^{12}]\) 中均匀分布的，则每个数的期望出现次数是 \(\frac{2 \times 10^{13}}{6 \times 10^{12}}=\frac{10}{3}\)，那么你选出 \(x\) 个子集和不重复的方案数就是 \(\binom{6 \times 10^{12}}{x} \times (\frac{10}{3})^x\)，总方案数是 \(\binom{2 \times 10^{13}}{x}\) 的，显然 \(x\) 很大的时候两者比值趋向 \(0\)，即能找到 \(x\) 个不重复的子集和的概率趋向 \(0\)，即 \(x\) 次随机后还不能找到解的概率几乎为 \(0\)。\(x\) 取 \(2 \times 10^7\) 就基本上一定有解了，至于时间，你放心，\(12\) 秒呢。
考虑不随机的时候，下证随机情况下期望枚举 \(x\) 的次数一定比不随机的大：假设这些子集和构成的集合为 \(T\)，每个数出现的次数为 \(c_i\)，则不重复的方案数为 \(\binom{|T|}{x} \times \prod_{i \in T} c_i\)。\(|T|\) 固定时由均值不等式，\(y_i\) 全相等时最大。如果将 \(|T|\) 变大，方案数也会变多。于是 \(|T|\) 最大，\(c_i\) 都相等时方案数最多，即均匀随机情况下期望枚举 \(x\) 的次数最大。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
// typedef __int128 i128;
typedef pair<int, int> pii;
const int N = 2e5 + 10, mod = 998244353;
template<typename T>
void dbg(const T &t) { cout << t << endl; }
template<typename Type, typename... Types>
void dbg(const Type& arg, const Types&... args) {cout << arg << ' ';dbg(args...);
}
namespace Loop1st {
int n;
ll a[N], sum[N];
map<ll, array<ll, 2>>mp;
map<ll, array<ll, 7>>buc;
void main(int tc) {cout << "Case #" << tc << ": "; buc.clear();mp.clear();cin >> n;for (int i = 0; i < n; i++) cin >> a[i];if (n == 20) {for (int s = 1; s < (1 << n); s++) {sum[s] = 0;for (int i = 0; i < n; i++) if (s >> i & 1) sum[s] += a[i];if (mp[sum[s]][0]) {cout << "Possible\n";int t = mp[sum[s]][1];for (int i = 0; i < n; i++) if (t >> i & 1) cout << a[i] << ' ';cout << '\n';for (int i = 0; i < n; i++) if (s >> i & 1) cout << a[i] << ' ';cout << '\n'; return ;}mp[sum[s]] = {1, s};}cout << "Impossible\n";} else {while (true) {int c1 = rand() % (n - 5);int c2 = rand() % (n - 5 - c1) + c1 + 1;int c3 = rand() % (n - 4 - c2) + c2 + 1;int c4 = rand() % (n - 3 - c3) + c3 + 1;int c5 = rand() % (n - 2 - c4) + c4 + 1;int c6 = rand() % (n - 1 - c5) + c5 + 1;// dbg("###", c1, c2, c3, c4, c5, c6);ll s = a[c1] + a[c2] + a[c3] + a[c4] + a[c5] + a[c6];array<ll, 7> cur = {1ll, a[c1], a[c2], a[c3], a[c4], a[c5], a[c6]};if (buc[s][0] && buc[s] != cur) {cout << "Possible\n";array<ll, 7> tmp = buc[s];cout << tmp[1] << ' ' << tmp[2] << ' ' << tmp[3] << ' ' << tmp[4] << ' ' << tmp[5] << ' ' << tmp[6] << '\n';cout << a[c1] << ' ' << a[c2] << ' ' << a[c3] << ' ' << a[c4] << ' ' << a[c5] << ' ' << a[c6] << '\n';return ;}buc[s] = cur;}}
}}
int main() {// freopen("data.in", "r", stdin);// freopen("data.out", "w", stdout);ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);srand(time(0));int T = 1;cin >> T;for (int tc = 1; tc <= T; tc++) Loop1st::main(tc);return 0;
}