Ｉ Ⅱ Ⅲ
26. 数论 H. [arc137_d]Prefix XORs
对于普通的前缀和，有 \(S_i^{(k)}=\sum_{j=1}^{i}{i-j+k-1\choose k-1}a_j\)，其中 \(S_i^{(k)}\) 表示 \(k\) 次前缀和后 \(a_i\) 的值。
那么对于异或和，\(a_i\) 对第 \(k\) 次的答案有贡献的充要条件即为 \({n-i+k-1\choose k-1}\equiv1\pmod{2}\)。由卢卡斯定理可知它的充要条件又是 \((n-i)\mathrm{bitand}(k-1)=0\)。于是第 \(k\) 个答案即为：
\[\sum_{i=1}^{n}a_i[(n-i)\subseteq\overline{(k-1)}]
\]
高维前缀和即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=(1<<20)+5;
int n,m,a[maxn];
int main(){ios::sync_with_stdio(0),cin.tie(0);cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[n-i];}for(int i=0;i<=19;i++){for(int S=0;S<1<<20;S++){if(S>>i&1){a[S]^=a[S^1<<i];}}}for(int i=0;i<m;i++){cout<<a[((1<<20)-1)^i]<<' ';}return 0;
}
}
int main(){return asbt::main();}