题目链接
题目解法
首先不知道 \(a_x+a_y+a_z+a_w\) 和 \(b_x\oplus b_y\oplus b_z\oplus b_w\) 肯定没法做，所以考虑求出和为 \(i\)，异或和为 \(j\) 的方案数
考虑 \(x,y,z,w\) 都是在 \([1,n]\) 的范围内任意选，所以不妨先考虑两个数和为 \(i\)，异或和为 \(j\) 的方案数
可以发现 \(i+j=k\) 时，\(i,j\) 合并到 \(k\) 的过程是 \(fwt\)
因为对于每一个 \(k\)，\(i+j\) 是等价的，所以我们可以直接将所有满足 \(i+j=k\) 的 \(i,j\)点值相乘之后累加
\(4\) 个数也可以类似 \(2\) 个数的方式合并
时间复杂度为 \(O(512^3)\)
#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 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);}
inline int read(){
int FF=0,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;
return FF*RR;
}
const int P=998244353,iv2=499122177;
int Cxor[2][2]={{1,1},{1,P-1}};
int ICxor[2][2]={{iv2,iv2},{iv2,P-iv2}};
const int N=100100;
int n,a[N],b[N];
int A[512][512],B[1024][512],C[2048][512];
void fwt(int *a,const int Mat[2][2]){
for(int mid=1;mid<512;mid<<=1)
for(int i=0;i<512;i+=mid<<1)
for(int j=0;j<mid;j++){
int x=a[i+j],y=a[i+j+mid];
a[i+j]=(1ll*x*Mat[0][0]+1ll*y*Mat[0][1])%P;
a[i+j+mid]=(1ll*x*Mat[1][0]+1ll*y*Mat[1][1])%P;
}
}
inline void inc(int &x,int y){ x+=y;if(x>=P) x-=P;}
int main(){
n=read();
F(i,1,n) a[i]=read();
F(i,1,n) b[i]=read();
F(i,1,n) A[a[i]][b[i]]++;
F(i,0,511) fwt(A[i],Cxor);
F(i,0,511) F(j,0,511) F(k,0,511) inc(B[i+j][k],1ll*A[i][k]*A[j][k]%P);
F(i,0,1023) F(j,0,1023) F(k,0,511) inc(C[i+j][k],1ll*B[i][k]*B[j][k]%P);
F(i,0,2047) fwt(C[i],ICxor);
int ans=0;
F(i,0,2047){
int mi=1;
F(j,0,511) inc(ans,1ll*mi*C[i][j]%P),mi=1ll*mi*i%P;
}
printf("%d\n",ans);
fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));
return 0;
}