专栏文章

CF1119H Triple

__ANIG_
CF1119H题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mio1da2f
此快照首次捕获于
2025/12/02 11:46
3 个月前
此快照最后确认于
2025/12/02 11:46
3 个月前
查看原文
传送门
首先一个显然的做法是直接 FWT。
设 Fi,j=FWT(fi)jF_{i,j}=FWT(f_i)_j，其中 fif_i 是只有 ai,bi,cia_i,b_i,c_i 三项分别是 x,y,zx,y,z 的数组。设 gi=∏j=1nFj,ig_i=\prod\limits_{j=1}^n F_{j,i}，则答案就是 IFWT(g)IFWT(g)。
由于 fif_i 非零项很少，考虑手动 FWT。
由于 FWT 是线性变换，所以 FWT(A+B)=FWT(A)+FWT(B)FWT(A+B)=FWT(A)+FWT(B)。
又由于 xor 卷积的变换系数是 (−1)∣i&j∣(-1)^{|i\&j|}，所以 Fi,j=(−1)∣j&ai∣x+(−1)∣j&bi∣y+(−1)∣j&ci∣zF_{i,j}=(-1)^{|j\&a_i|}x+(-1)^{|j\&b_i|}y+(-1)^{|j\&c_i|}z。
为了简便，可以将 {ai,bi,ci}\{a_i,b_i,c_i\} 变换为 {0,ai⊕bi,ai⊕ci}\{0,a_i\oplus b_i,a_i\oplus c_i\}，最终答案 xor 上所有 aia_i 即可。
考虑如何求 gg。
gj=∏i=1n[x+(−1)∣j&bi∣y+(−1)∣j&ci∣z]g_j=\prod\limits_{i=1}^n[x+(-1)^{|j\&b_i|}y+(-1)^{|j\&c_i|}z]
枚举 y,zy,z 的符号，问题转化为形如求有多少个 ii，满足 (−1)∣j&bi∣=1(-1)^{|j\&b_i|}=1 且 (−1)∣j&ci∣=1(-1)^{|j\&c_i|}=1。
也就是 ∑i=1n[(−1)∣j&bi∣=1][(−1)∣j&ci∣=1]\sum\limits_{i=1}^n[(-1)^{|j\&b_i|}=1][(-1)^{|j\&c_i|}=1]。
注意到，[(−1)x=1]=(−1)x+12[(-1)^x=1]=\frac{(-1)^x+1}{2}。
要求的就转化为 14∑i=1n[(−1)∣j&bi∣+1][(−1)∣j&ci∣+1]\frac 14\sum\limits_{i=1}^n[(-1)^{|j\&b_i|}+1][(-1)^{|j\&c_i|}+1]。
拆括号得：
14∑i=1n(−1)∣j&bi∣(−1)∣j&ci∣+∑i=1n(−1)∣j&bi∣+∑i=1n(−1)∣j&ci∣+n\frac 14\sum\limits_{i=1}^n(-1)^{|j\&b_i|}(-1)^{|j\&c_i|}+\sum\limits_{i=1}^n(-1)^{|j\&b_i|}+\sum\limits_{i=1}^n(-1)^{|j\&c_i|}+n
注意到 (−1)∣x&a∣(−1)∣x&b∣=(−1)∣x&(a⊕b)∣(-1)^{|x\&a|}(-1)^{|x\&b|}=(-1)^{|x\&(a\oplus b)|}。
于是问题等价于求 ∑i=1n(−1)∣j&Xi∣\sum\limits_{i=1}^n(-1)^{|j\&X_i|}。
设 hi,j=(−1)∣j&Xi∣h_{i,j}=(-1)^{|j\&X_i|}，wi,j=[j=Xi]w_{i,j}=[j=X_i]，则 hi=FWT(wi)h_{i}=FWT(w_i)。
要求的相当于 ∑i=1nhi\sum\limits_{i=1}^nh_i，也就是 ∑i=1nFWT(wi)=FWT(∑i=1nwi)\sum\limits_{i=1}^n FWT(w_i)=FWT(\sum\limits_{i=1}^nw_i)。
于是，我们在 O(k2k)O(k2^k) 解决了该问题。
CPP
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1.4e5+5,mods=998244353;
int pows(int a,int b){
	if(b==0)return 1;
	int res=pows(a,b>>1);
	res=res*res%mods;
	if(b&1)res=res*a%mods;
	return res;
}
int n,k,x,y,z,a[N],b[N],c[N],al,f[4][N];
void fwt(int*p,int n,int w00,int w01,int w10,int w11){
	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 t0=p[i+j],t1=p[i+j+mid];
				p[i+j]=(t0*w00+t1*w10)%mods;
				p[i+j+mid]=(t0*w01+t1*w11)%mods;
			}
		}
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>k>>x>>y>>z;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i]>>c[i];
		b[i]^=a[i];c[i]^=a[i];
		al^=a[i];
		f[1][b[i]]++;
		f[2][c[i]]++;
		f[3][b[i]^c[i]]++;
	}
	fwt(f[1],1<<k,1,1,1,-1);
	fwt(f[2],1<<k,1,1,1,-1);
	fwt(f[3],1<<k,1,1,1,-1);
	for(int i=0;i<(1<<k);i++){
		int tmp00=(f[3][i]+f[2][i]+f[1][i]+n)/4,tmp01=(-f[3][i]-f[2][i]+f[1][i]+n)/4,tmp10=(-f[3][i]+f[2][i]-f[1][i]+n)/4,tmp11=(f[3][i]-f[2][i]-f[1][i]+n)/4;
		f[0][i]=pows((x+y+z)%mods,tmp00)*pows((x+y-z)%mods,tmp01)%mods*pows((x-y+z)%mods,tmp10)%mods*pows((x-y-z)%mods,tmp11)%mods;
	}
	fwt(f[0],1<<k,499122177,-499122176,499122177,-499122177);
	for(int i=0;i<(1<<k);i++)cout<<(f[0][i^al]%mods+mods)%mods<<" ";
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...