题解 CF1713F【Lost Array】

首先，为了方便将第 \(1\) 行的数从右往左重标号为 \(0, 1, \cdots, n - 1\)。我们发现 \((1, i)\) 对于 \((j,n+1)\) 的贡献是 \(C(i + j, i) \pmod 2\)，根据 \(\text{lucas}\) 定理可得有贡献当且仅当 \(i\ \text{and}\ j = 0\)。

考虑容斥，枚举 \(k\)，钦定 \(i\ \text{and}\ j\) 在二进制下为 \(k\) 的超集。令 \(i\ \text{and}\ j=t\)，则会被贡献次数为 \(2^{\text{popcount}(k)}\)。于是，直接异或即可。

时间复杂度 \(O(n^{\log_2{3}})\approx O(n^{1.585})\)，大概是 \(10^9\) 次的位运算，但由于是位运算，所以可以稳过。（另外观察到对于不同的 \(i\) 可以高位前缀和得到一样的结果）

#include <bits/stdc++.h>
#define SZ(x) (int) x.size() - 1
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); }
template <typename T> void read(T &x) {
	x = 0; int f = 1; char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
const int N = 5e5 + 10;
int b[N], t[N];
signed main() {
	int n; read(n);
	for (int i = 0; i < n; ++i) read(b[i]);
	int lg = log2(n);
	for (int i = 0; i < n; ++i) {
		t[i] = b[0];
		for (int j = i; j; j = (j - 1) & i) t[i] ^= b[j];
	}
	F(l, 0, lg)
		for (int i = 0; i < n; ++i)
			if ((i >> l) & 1) t[i ^ (1 << l)] ^= t[i];
	for (int i = n - 1; ~i; --i) cout << t[i] << " ";
	return 0;
}