【Codeforces 1119H】Triple
FWT。
题目大意：
给定 $n,k,x,y,z$，你有 $n$ 个三元组 $(a_i,b_i,c_i)$，表示第 $i$ 个数组中 $a_i$ 有 $x$ 个，$b_i$ 有 $y$ 个，$c_i$ 有 $z$ 个。保证 $a_i,b_i,c_i\lt 2^k$。
现在求从这 $n$ 个数组中，每个里选择一个数。求选择的数的异或和为 $0\sim 2^{l-1}$ 的方案数分别是多少。
题解：
定义 $\oplus$ 表示异或运算。
一个比较显然的暴力：对每个数组，令 $f_{i}[a_i]=x,f_{i}[b_i]=y,f_{i}[c_i]=z$，然后对所有 $f_i$ 进行 FWT 后点乘再 FWT 回来。时间复杂度 $O(2^m\times nm)$。
考虑 FWT 的实质。FWT 是对原数组的一个线性变换，满足 $F’[k]=\sum_i(-1)^{\mathrm{popcount}(k\& i)}F[i]$。
对于本题，我们有 $F’[k]=(-1)^{\mathrm{popcount}(k\& a_i)}x+(-1)^{\mathrm{popcount}(k\& b_i)}y+(-1)^{\mathrm{popcount}(k\& c_i)}z$
由于每个数组中原来只有 $3$ 个位置有值，所以 FWT 后的数组中，可能的取值只有 $2^3=8$ 种。
进一步地，我们令 $b_i=b_i\oplus a_i,c_i=c_i\oplus a_i,a_i=0$，然后令 $f_{i}[a_i]=x,f_{i}[b_i]=y,f_{i}[c_i]=z$，最后得到的结果的数组的每个位置异或上原来所有 $a_i$ 的异或和后就是它的实际位置。
这样做的好处是，$0$ 按位与上任何数，其结果都为 $0$。所以 $x$ 前面的系数一定是 $1$。
那么 FWT 完，每个位置的值就是 $x+y+z,x-y+z,x+y-z,x-y-z$ 中的一种。
由于我们要求最终数组的每个点的点值，所以我们考虑求出位置 $i$，上述四种值分别出现了多少次。
假设出现次数分别为 $c_1,c_2,c_3,c_4$。
首先有 $c_1+c_2+c_3+c_4=n$。
考虑列方程组解出 $c_1,c_2,c_3,c_4$。
我们令 $(x,y,z)=(0,1,0)$，然后观察 FWT 后的结果：
$F’[k]=(-1)^{\mathrm{popcount}(k\& b_i)}$，其中，在 $c_1,c_2,c_3,c_4$ 中的 $y$ 分别会产生 $1,-1,1,-1$ 的贡献。因此 $c_1-c_2+c_3-c_4=(-1)^{\mathrm{popcount}(k\& b_i)}$。
同理可得 $c_1+c_2-c_3-c_4=(-1)^{\mathrm{popcount}(k\& c_i)}$。
还差一个数组，我们令 $F[b_i\oplus c_i]=1$，然后观察 FWT 后的结果。$F’[k]=(-1)^{\mathrm{popcount}(k\& (b_i\oplus c_i))}=(-1)^{\mathrm{popcount}((k\& b_i)\oplus (k\&c_i))}$。
考虑 $c_1,c_2,c_3,c_4$ 中每对 $y,z$ 的贡献，分别会对其产生 $1,-1,-1,1$ 的贡献（两个符号的异或）。
我们有四个方程组，就可以解四个未知数了。
另外可以发现这些方程组的系数和 FWT 的变换系数是一样的，因此解方程组可以直接点值做 IFWT。当然本题未知数个数少，可以直接 $O(1)$ 计算。
这是对于单个数组。又由于 $\mathrm{FWT}(A+B)=\mathrm{FWT}(A)+\mathrm{FWT}(B)$，所以对于多个数组的情况，我们把对应的 $b_i,c_i,b_i\oplus c_i$ 加一，然后 FWT 变换即可得到每个位置的和。其中 $c_1+c_2+c_3+c_4=n$。解出来后进行快速幂即可得到每个位置的 FWT 后的值。
最后再做一次 IFWT 即可。
时间复杂度 $O(n+2^kk)$。
Code：
#include<cstdio>
typedef long long LL;
const int md=998244353,N=1<<17,iv2=md+1>>1,iv4=(LL)iv2*iv2%md;
int n,k,p,x,y,z,a,b,c,A,B,C,D,f1[N],f2[N],f3[N],F[N];
void _v(int*a,const int&C,const int&v=1){
for(int i=1;i<C;i<<=1)
for(int j=0;j<C;j+=i<<1)
for(int k=0;k<i;++k){
const int x=a[j+k],y=a[j+k+i];
a[j+k]=(LL)(x+y)*v%md,a[j+k+i]=(LL)(x-y+md)*v%md;
}
}
#define FWT(a)_v(a,1<<k,1)
#define IFWT(a)_v(a,1<<k,iv2)
inline int pow(int a,int b){int r=1;for(;b;b>>=1,a=(LL)a*a%md)if(b&1)r=(LL)r*a%md;return r;}
int main(){
scanf("%d%d%d%d%d",&n,&k,&x,&y,&z);
A=((LL)x+y+z)%md,B=((LL)x-y+z+md)%md,C=((LL)x+y-z+md)%md,D=((LL)x-y-z+md*2)%md;
for(int i=0;i<n;++i){
scanf("%d%d%d",&a,&b,&c);
p^=a,b^=a,c^=a;
++f1[b],++f2[c],++f3[b^c];
}
FWT(f1),FWT(f2),FWT(f3);
for(int i=0;i<1<<k;++i){
int c1=((LL)n+f1[i]+f2[i]+f3[i])%md*iv4%md;
int c2=((LL)n-f1[i]+f2[i]-f3[i]+2*md)%md*iv4%md;
int c3=((LL)n+f1[i]-f2[i]-f3[i]+2*md)%md*iv4%md;
int c4=((LL)n-f1[i]-f2[i]+f3[i]+2*md)%md*iv4%md;
F[i]=(LL)pow(A,c1)*pow(B,c2)%md*pow(C,c3)%md*pow(D,c4)%md;
}
IFWT(F);
for(int i=0;i<1<<k;++i)printf("%d ",F[i^p]);
return 0;
}