神仙题啊...
题意
将原集合划分成$ A,B,C$三部分，要求满足$ A,B$不全为空且$ A$的异或和等于$ B$的异或和
求方案数
集合大小 $n\leq 10^6$ 值域$val \leq 10^6$
题解
如果要满足$ A,B$的异或和相同，必然有$ A \cup B$中所有元素异或和为$ 0$
如果存在这样一个集合$ A \cup B$，这之中的每个元素可以在集合$ A$中也可以在集合$ B$中
即对答案产生$ 2^{|A|+|B|}$的贡献
设每个元素$ a_i$的多项式为$ 2x^{a_i}+1$
则答案相当于所有多项式的异或卷积结果的常数项的值减一(减去A,B全为空的情况)
用$ FWT$优化这个卷积，复杂度是$ O(n·val·\log val)$
并得不了什么分
打表发现这类多项式的$ FWT$结果只有$ -1$和$ 3$两种数
$ FWT$有一个性质是$ FWT$的和等于和的$ FWT$
因此我们先对所有多项式求和，再做一次$ FWT$
这时候的$ FWT$结果可以被$ (-1)x+3(n-x)$表示
这样可以求出原先这个位置中$ -1$和$ 3$的数量
就能求出原先数组的$ FWT$之后的对应位乘积的值了
得到$ FWT$数组后$ O(n)$计算答案即可
时间复杂度$ O(n \log n)$
代码
有过一些恶意卡常
#include<ctime>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#define p 998244353
#define file(x)freopen(x".in","r",stdin);freopen(x".out","w",stdout)
#define rt register int
#define ll long long
#include<sys/mman.h>
using namespace std;
struct ano{
char*s;
ano():s((char*)mmap(,<<,,,,)){}
operator int(){
int x=;
while(*s<)++s;
while(*s>)
x=x*+*s++-;
return x;
}
}buf;
int k,m,n,x,y,z,cnt,ans,invn;
int ksm(int x,int y=p-){
int ans=;
for(rt i=y;i;i>>=,x=1ll*x*x%p)if(i&)ans=1ll*ans*x%p;
return ans;
}
int A[];
int mi[],fla[];
int main(){
n=buf;int lim=,mc=;
for(rt i=;i<=n;i++)x=buf,A[]++,A[x]+=,mc=max(mc,x);
while(lim<=mc)lim<<=;
mi[]=;for(rt i=;i<=n;i++)mi[i]=1ll*mi[i-]*%p;
for(rt i=;i<lim;i<<=)
for(rt j=;j<lim;j+=i<<)
for(rt k=;k<i;k++){
const int x=A[j+k],y=A[i+j+k];
A[j+k]=x+y;A[i+j+k]=x-y;
}
int inv4=ksm();
for(rt i=;i<lim;i++){
x=(3ll*n-A[i])*inv4%p;
(ans+=mi[n-x]*((x&)?-:))%=p;
}
ans=1ll*ans*ksm(lim,p-)%p;
cout<<(ans+p-)%p;
return ;
}