专栏文章

P13497 【MX-X14-T7】墓碑密码

FForgotMe
P13497题解参与者 3已保存评论 3

文章操作

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

当前评论
3 条
当前快照
1 份
快照标识符
@miop06ek
此快照首次捕获于
2025/12/02 22:47
3 个月前
此快照最后确认于
2025/12/02 22:47
3 个月前
查看原文
有点不太像题了，感觉非常诡异，写之前真没觉得能过。
显然如果可以求出 dpidp_i 表示 SS 中选出 ii 个数异或和在 TT 的方案数，那么就容易快速回答一次询问，就是 ∑i=0∣S∣dpi(⌊∣S∣−i2⌋+∣S∣∣S∣)\sum_{i=0}^{|S|} dp_i\binom{\lfloor\frac{|S|-i}{2}\rfloor+|S|}{|S|}。
问题在于如何快速求出 dpidp_i。考虑 FWT，设集合幂级数 A=∏a∈S(1+yxa)A=\prod_{a\in S}(1+yx^{a})，其中 yy 这一元表示已选的数的个数，那么就是要求 ∑v∈T[xv]A\sum_{v\in T}[x^v]A。根据 FWT 那一套的理论，[xa]FWT(A)=∑i=02L−1(−1)∣a∩i∣Ai[x^a]FWT(A)=\sum_{i=0}^{2^L-1}(-1)^{|a\cap i|}A_i，[xa]IFWT(A)=2−L∑i=02L−1(−1)∣a∩i∣Ai[x^a]IFWT(A)=2^{-L}\sum_{i=0}^{2^L-1}(-1)^{|a\cap i|}A_i。
于是容易写出更加直接的答案：
2−L∑v∈T∑w=02L−1(−1)∣w∩v∣∏a∈S(1+y(−1)∣w∩a∣)2^{-L}\sum_{v\in T}\sum_{w=0}^{2^L-1}(-1)^{|w\cap v|} \prod_{a\in S} (1+y(-1)^{|w\cap a|})
计算上式也很简单，先对于每个 ww 求出 ∑v∈T(−1)∣w∩v∣\sum_{v\in T}(-1)^{|w\cap v|}。又因为 ∏a∈S(1+y(−1)∣w∩a∣)\prod_{a\in S} (1+y(-1)^{|w\cap a|}) 这一项本质上只有 ∣S∣|S| 种值，形如 (1+y)k(1−y)∣S∣−k(1+y)^k(1-y)^{|S|-k}，于是只需要求出对于每一种 kk 的系数和即可，最后使用二项式定理暴力展开即可得到 dpidp_i。容易做到 O((∣S∣+∣T∣)max⁡{Si,Ti})\mathcal{O}((|S|+|T|)\max\{S_i,T_i\})。
由于 ∣S∣,∣T∣≤128|S|,|T|\le 128，考虑用两个 64 位二进制数（拼成一个 128 位二进制数）去存当 ww 固定时，∣w∩Si∣|w\cap S_i| 的奇偶性，然后从小到大递推转移，转移容易做到线性，每次从删除最低位的状态转移即可。
但是这样子空间爆炸了，实际上也容易解决，枚举 ww 的前 88 位是啥，那么就只需要开一个 2202^{20} 的数组了。
最后回答询问有一些细节需要处理，如果每次暴力 O(∣S∣)\mathcal{O}(|S|) 算组合数，那么就是 O(q∣S∣2)\mathcal{O}(q|S|^2)。一种解决方法是直接预处理 5×108+∣S∣5\times 10^8+|S| 以内的阶乘，由于本题不卡空间，所以开的下。另外一种就是注意到 ⌊∣S∣−i2⌋\lfloor\frac{|S|-i}{2}\rfloor 的变化量是 O(∣S∣)\mathcal{O}(|S|) 的，所以每次暴力移动区间乘积也行，但是还是要算一个数的逆元，所以会带 log，好像过不去。
时间复杂度 O(max⁡{Si,Ti}+q∣S∣+∣S∣3)\mathcal{O}(\max\{S_i,T_i\}+q|S|+|S|^3)。
给个部分代码，正常写就能直接过，常数很小。
CPP
int n,m,q,a[205],b[205],g[205],dp[205];
ull f1[(1<<20)+5],f2[(1<<20)+5],f3[(1<<20)+5],f4[(1<<20)+5],sta1[25],sta2[25],sta3[25],sta4[25];
int sf[50000205];
inline void solveit(int v){
	f1[0]=f2[0]=f3[0]=f4[0]=0;
	for(int i=0;i<min(64,n);i++)
		if(__builtin_popcountll(v&a[i])&1)f1[0]|=(1ull<<i);
	for(int i=64;i<n;i++)
		if(__builtin_popcountll(v&a[i])&1)f2[0]|=(1ull<<(i-64));
	for(int i=0;i<min(64,m);i++)
		if(__builtin_popcountll(v&b[i])&1)f3[0]|=(1ull<<i);
	for(int i=64;i<m;i++)
		if(__builtin_popcountll(v&b[i])&1)f4[0]|=(1ull<<(i-64));
	for(int i=0;i<(1<<20);i++){
		if(i){
			int p=i^(i&-i),x=__builtin_ctz(i);
			f1[i]=(f1[p]^sta1[x]);
			f2[i]=(f2[p]^sta2[x]);
			f3[i]=(f3[p]^sta3[x]);
			f4[i]=(f4[p]^sta4[x]);	
		}
		int c=__builtin_popcountll(f1[i])+__builtin_popcountll(f2[i]);
		int c2=__builtin_popcountll(f3[i])+__builtin_popcountll(f4[i]);
		int v=dec(m,2*c2);
		g[c]=add(g[c],v);
	}
}
inline void solve(){
	gi(n),gi(m);
	for(int i=0;i<n;i++)gi(a[i]);
	for(int i=0;i<m;i++)gi(b[i]);
	for(int i=0;i<20;i++){
		for(int j=0;j<min(64,n);j++)if((1<<(i+8))&a[j])sta1[i]|=(1ull<<j);
		for(int j=64;j<n;j++)if((1<<(i+8))&a[j])sta2[i]|=(1ull<<(j-64));
	}
	for(int i=0;i<20;i++){
		for(int j=0;j<min(64,m);j++)if((1<<(i+8))&b[j])sta3[i]|=(1ull<<j);
		for(int j=64;j<m;j++)if((1<<(i+8))&b[j])sta4[i]|=(1ull<<(j-64));
	}
	for(int w=0;w<(1<<8);w++)solveit(w);
	int xs=qkpow((1<<28),mod-2);
	for(int i=0;i<=n;i++){
		for(int j=0;j<=i;j++){
			for(int k=0;k<=n-i;k++){
				int v=1ll*binom(i,j)*binom(n-i,k)%mod*g[i]%mod;
				if(j&1)dp[j+k]=dec(dp[j+k],v);
				else dp[j+k]=add(dp[j+k],v);
			}
		}
	}
	gi(q);
	while(q--){
		int N;
		gi(N);
		int res=0;
		for(int i=0;i<=n;i++){
			if(N>=i){
				int lim=(N-i)/2;
				int pro=1ll*fac[lim+n]*inv[lim]%mod;
				res=add(res,1ll*pro*inv[n]%mod*dp[i]%mod);
			}
		}
		pi(1ll*res*xs%mod);
	}
}

评论

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

正在加载评论...