题目链接
题目解法
很牛的题！！！
先考虑 \((0,i)\) 对 \((j,n)\) 的贡献，因为是异或，所以只要考虑奇偶性
问题可以抽象成一条路径对应 \(a_i\) 的贡献，所以是否有 \(a_i\) 的贡献看 \(\binom{n-i+j-1}{j-1}\) 的奇偶性
根据 \(kummer\) 定理，这个组合数是奇数当且仅当 \(n-i+j-1\) 是 \(j-1\) 的超集，等价于 \((n-i)\&(j-1)=0\)
令新的 \(i'=n-i,j'=j-1\)（下面仍以 \(i,j\) 代指 \(i',j'\)）
接下来的我的思路就和正解不一样了
考虑 \(b_j\) 的值是 \(j\) 的补集的子集的 \(a\) 之和，这个东西看似可以还原
但有一点没考虑到：如果要还原的话，\(b\) 必须是满的 \(2\) 的次幂项，否则前面会有 \(0\)
这就直接 \(ban\) 掉了这个做法
换个角度想
限制是 \(i\&j=0\)，不妨容斥 \(i\&j\) 是 \(k\) 的超集
令 \(c_i\) 为满足 \(i|j\) 的 \(a_j\) 的异或和，即 \(c\) 是 \(a\) 的高维后缀异或和
则 \(b\) 不难发现为 \(c\) 的高维前缀异或和
把操作反过来，因为异或的和与差是一样的，所以先做一遍高维后缀异或和，在做高维前缀异或和就可以还原出 \(a\)，时间复杂度 \(O(n\log n)\)
感觉容斥直接把思路打开了
#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
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 &FF){
FF=0;int RR=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
FF*=RR;
}
const int N=500010;
int n,f[N];
int main(){
read(n);
int lg=log2(n);
F(i,0,n-1) read(f[i]);
F(i,0,lg) F(j,0,n-1) if(j>>i&1) f[j]^=f[j-(1<<i)];
F(i,0,lg) F(j,0,n-1) if(j>>i&1) f[j-(1<<i)]^=f[j];
DF(i,n-1,0) printf("%d ",f[i]);puts("");
return 0;
}