2021 Summer Petrozavodsk Camp, Day 3: IQ test (XXII Open Cup, Grand Prix of IMO)
A （性质，转化）
发现如果存在 \(b\) 中存在 \(0\)，那么直接构造 \(b_1, 0, b_2, 0, \dots, b_n, 0\) 即可。
如法炮制，考虑 \(b\) 中所有数的 \(and\)。
有解当且仅当 \(and\) 在 \(b\) 中出现过。
- 充分性：构造 \(b_1, and, b_2, and, \dots, and, b_n\)
- 必要性：可以发现 \(b\) 中所有数的 \(and\) 必然对应 \(and a_1, \dots, a_n\)。不存在的话肯定这组 \(b\) 无解。
E（随机化）
存在欧拉回路当且仅当所有节点的度数为偶数。先问出一共的边数 \(m\)。
考虑随机一个点集 \(S\)，问出 \(S, {1, 2, \dots, n} \ S\) 的边数 \(a, b\)。（随机每个点的概率都是 1/2）
那么这两个点集合之间的边数就是 \(m - a - b\)。
注意到，\(S\) 中度数和的奇偶性就是 \(m - a - b\) 的奇偶性，因为 \(S\) 中的边贡献 \(2\)，\(m - a - b\) 贡献 \(1\)。
- \(m - a - b\) 为奇数，那么肯定存在某个点度数为奇数，puts("NO")。
- \(m - a - b\) 为偶数，那么你说这可能会有两个度数为奇数的点导致和还是偶数，那么这种情况发生的概率是 \(\dfrac{1}{2}\)，因为只要在随机 \(S\) 时让其中一个点去到另一个集合即可。也就是说错误的概率是 \(\dfrac{1}{2}\)。虽然有 \(\dfrac{1}{4}\) 的概率又错了，还有 \(\dfrac{1}{8}\) 的概率又对了，但是我感觉这后面也是指数减小的，所以可以忽略后面的概率。
那么迭代 \(29\) 次，正确的概率就是 \(1 - \dfrac{1}{2^{29}}\)。
Summary : 看到这种不明显的 log 次询问题，可以想想随机化错误概率非常小的情况。
而判断每个数是否是偶数，可以随机点集判断和的奇偶性转换。
类似的题 CF1746F。
F（性质，转换）
容易发现有解等价于 \(a + b \equiv c + d \pmod P\)。因为变换不会改变 \(a+b\) 的奇偶性。
那么其实只要考虑 \(a\) 能不能变换成 \(c\)。
变换等价于 \(a \to 2a\) 和 \(a \to 2a - s\)。
会发现 \(-s\) 很麻烦。
trick 是 两边同时乘 \(s\) 的逆元。这样就变成 \(a\to 2a, a\to 2a - 1\)，问能不能变成 \(c\)。
会发现这个过程迭代 \(30\) 次，总长度会超过 \(2^{30} \ge P\) 也就是在 \(F_P\) 的剩余系下全都覆盖到了。
于是答案不超过 \(30\)。
枚举答案，我们会得到一个区间 \(l, r\)，因为是在模一下，如果 \(l > r\) 那么要求 \(r \le c\) 或 \(c \le l\)，否则就是 \(c \in [l, r]\)。
Summary：等价转化，特别是同除以 \(s\)，这样就能让取值集合成为一段区间。
M (数学，不等式，调和级数)
设 \(a_i^2 + a_j = k^2\)
那么 \(k = \sqrt{a_i^2 + a_j} \le a_i + \sqrt{a_j}\)
枚举 \(i,k\)，那么复杂度是 \(n\sqrt{a_i}\)。
\(ans += cnt[k^2 - a_i^2]\)
这里 \(k\) 的迭代从 \(a_i + 1 \to a_i + 1000\)
那么也就是 \(ans += cnt[(t + a_i)^2 - a_i^2] = cnt[t ^ 2 + a_i ^ 2 - a_i ^ 2 + 2 a_i t] = cnt[t^2 + 2a_it]\)
由于 \(a_i\) 互不相同，你会发现暴力就是调和级数的复杂度，因为要求 \(cnt\) 中的数 \(\le 10^6\)。
signed main() {
n = read();
for(int i = 1; i <= n; ++ i) {
a[i] = read();
cnt[a[i]] ++ ;
}
int ans = 0;
for(int i = 1; i <= n; ++ i) {
for(int k = 1; k <= 1000 && k * k + 2 * a[i] * k <= 1000000 ; ++ k) {
ans += cnt[k * k + 2 * a[i] * k];
}
}
cout << ans;
return 0;
}