CF1119H Triple

异或卷积，把一个三元组 \(\{a_i,b_i,c_i\}\) 转化为 \(F_i[a_i]=x\)，\(F_i[b_i]=y\)，\(F_i[c_i]=z\) 的幂级数，将 \(\prod\limits_{i=1}^n \text{FWT}(F_i)\) 执行 \(\text{IFWT}\) 即可

考虑从每个幂级数只有 \(3\) 个非零值入手优化，设 \(c(i,j)\) 表示异或卷积的变换系数，即 \(\text{FWT}(F_k)[i]=\sum\limits_{i=0}^{m-1} c(i,j) F_k[j]\)，构造可得 \(c(i,j)=(-1)^{\text{bitcnt}(i \wedge j)}\)，则 \(\text{FWT}(F_k)[i]\) \(=(-1)^{\text{bitcnt}(i\wedge a_k)}x+(-1)^{\text{bitcnt}(i\wedge b_k)}y+(-1)^{\text{bitcnt}(i\wedge c_k)}z\)

令 \(S_i=\prod\limits_{k=1}^n \text{FWT}(F_k)[i]\)，考虑对每个 \(S_i\) 求出 \(\text{FWT}(F_k)[i]\) 后的乘积项 \(8\) 种情况的个数，此时利用异或的自反性化简问题，将每个三元组 \(\{a_i,b_i,c_i\}\) 异或 \(a_i\) 变为 \(\{0,a_i \oplus b_i,a_i\oplus c_i\}\)，而最终结果的变化反映到幂级数上就是异或 \(\bigoplus\limits_{i=1}^n a_i\) 的下标映射，令 \(x+y+z\)，\(x+y-z\)，\(x-y+z\)，\(x-y-z\) 这 \(4\) 种情况的方案数为 \(c_i\)

考虑列出 \(4\) 个方程求解 \(c_i\)，显然 \(c_1+c_2+c_3+c_4=n\)

如果仅令 \(F_k[b_k]=1\)，有 \(\text{FWT}(F_k)[i]=(-1)^{\text{bitcnt}(i \wedge b_k)}\)，根据上式 \(y\) 的符号可得 \(\sum\limits_{i=1}^n \text{FWT}(F_k)[i]=c_1+c_2-c_3-c_4\)，而 \(\text{FWT}\) 是线性变化，由 \(\text{FWT}(x+y)=\text{FWT}(x)+\text{FWT}(y)\) 可快速求得原式权值

同理仅令 \(F_k[c_k]=1\) 可得 \(c_1-c_2+c_3-c_4\) 的权值

如果仅令 \(F_k[b_k \oplus c_k]=1\)，相当于将以上两种情况卷积，即 \(\text{FWT}(F_k)[i]=(-1)^{\text{bitcnt}(i \wedge b_k)}(-1)^{\text{bitcnt}(i \wedge c_k)}\)，可得 \(c_1-c_2-c_3+c_4\) 的权值，解出后维护出 \(\text{IWFT}(S)\) 即可求出答案

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,a,b,c,w;
ll x,y,z,f[131072],g[131072],h[131072],s[131072];
const int mod=998244353,inv=mod+1>>1;
ll qpow(ll a,ll b){
	ll s=1;
	for(a=(a%mod+mod)%mod;b;b>>=1,a=a*a%mod) if(b&1) s=s*a%mod;
	return s;
}
void fwt(ll *f,ll c){
	for(int k=1;k<m;k<<=1){
		for(int i=0;i<m;i+=k+k){
			for(int j=i;j<i+k;j++){
				ll x=f[j],y=f[j+k];
				if(c) f[j]=x+y,f[j+k]=x-y;
				else f[j]=(x+y)*inv%mod,f[j+k]=(x-y+mod)*inv%mod;
			}
		}
	}
}
int main(){
	scanf("%d%d%lld%lld%lld",&n,&m,&x,&y,&z),m=1<<m;
	for(int i=1;i<=n;i++) scanf("%d%d%d",&a,&b,&c),w^=a,b^=a,c^=a,f[b]++,g[c]++,h[b^c]++;
	fwt(f,1),fwt(g,1),fwt(h,1);
	for(int i=0;i<m;i++){
		ll c=(n+f[i]+g[i]+h[i])/4;
		s[i]=qpow(x+y+z,c)*qpow(x+y-z,(n+f[i]-c*2)/2)%mod*qpow(x-y+z,(n+g[i]-c*2)/2)%mod*qpow(x-y-z,(n+h[i]-c*2)/2)%mod;
	}
	fwt(s,0);
	for(int i=0;i<m;i++) printf("%lld ",s[i^w]);
	return 0;
}