刚考完省选回来的时候搬的模拟赛的题。看到一道长的很类似的题所以把题解蒯过来。
首先对于每个异或和为 \(0\) 的子集 \(T\)，贡献为 \(2^{|T|}\)。答案就是把他们加起来然后减掉 \(1\)，是两个都不选的。
那么有一个浅显的 dp：\(dp_{i,j}\) 为考虑前 \(i\) 个元素，异或和为 \(j\) 的贡献和，那么转移：
\[dp_{i,j}=dp_{i-1,j}+dp_{i-1,j\oplus a_i} \]若设 \(F_i\) 为 \(dp_i\) 的集合幂级数，则有
\[F_i=F_{i-1}\times(x^{\varnothing}+2x^{a_i}) \]\(\times\) 为异或卷积。
此时我们把答案写成了异或卷积的形式。考虑 \(\text{FWT}(x^{\varnothing}+2x^{a_i})_j\) 的值，根据定义可以得到是：
\[\text{FWT}(x^{\varnothing}+2x^{a_i})_j= \begin{cases} -1\qquad &(|a_i\cap j|\bmod 2=1)\\ 3 &(|a_i\cap j|\bmod 2=0) \end{cases} \]那么只要算一下 \(a_i\cap j\bmod 2=1\) 的个数，随便统计一下就行了。
转化一下，设 \(cnt_i\) 为 \(i\) 的个数，那么可以直接求 \(\sum_{i}(-1)^{i\cap j}b_j\) 然后解方程得到个数。只需要一次 FWT。
#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;
const int mod=998244353;
int n,ans,a[1<<20],pw[1<<20];
int qpow(int a,int b){
int ans=1;
while(b){
if(b&1)ans=1ll*ans*a%mod;
a=1ll*a*a%mod;
b>>=1;
}
return ans;
}
void fwt(int a[],int n){
for(int mid=1;mid<n;mid<<=1){
for(int i=0;i<n;i+=mid<<1){
for(int j=0;j<mid;j++){
int x=a[i+j],y=a[i+j+mid];
a[i+j]=x+y;a[i+j+mid]=x-y;
}
}
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
int x;scanf("%d",&x);a[x]++;
}
pw[0]=1;
for(int i=1;i<(1<<20);i++)pw[i]=3ll*pw[i-1]%mod;
fwt(a,1<<20);
for(int i=0;i<(1<<20);i++){
int cnt=(a[i]+n)>>1;
if(n-cnt&1)ans=(ans-pw[cnt]+mod)%mod;
else ans=(ans+pw[cnt])%mod;
}
ans=1ll*ans*qpow(1<<20,mod-2)%mod-1+mod;
printf("%d\n",ans%mod);
return 0;
}