专栏文章

CF2075E XOR Matrix 题解 数位dp

DDemoe
CF2075E题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mipq7erj
此快照首次捕获于
2025/12/03 16:09
3 个月前
此快照最后确认于
2025/12/03 16:09
3 个月前
查看原文
题目传送门\large\text{题目传送门}

Description\text{Description}

  • 求整数数列 (a,b)(a,b) 对数满足集合 {ai⊕bj}\{a_i\oplus b_j\} 不超过 22 个元素。（其中 ⊕\oplus 代表位异或）
  • 其中 aa 长度为 nn，值域为 [0,A][0,A]；bb 长度为 mm，值域为 [0,B][0,B]。
  • 多测，答案对 998244353998244353 取模。
  • n,m,A,B≤229−1n,m,A,B\le 2^{29}-1。

Solution\text{Solution}

显然若存在 ai≠aja_i\ne a_j，则有 ai⊕bk≠aj⊕bka_i\oplus b_k\neq a_j\oplus b_k。
而最终集合不超过 22 个元素，则可知整数数列 aa 和 bb 中也各自最多有 22 个不同的数值。
那么就分作四大类讨论：

aa 和 bb 都为常数列

显然贡献为 (A+1)×(B+1)(A+1)\times (B+1)。

aa 非常数列 bb 为常数列

剔除掉 aa 为常数列的可能，贡献为 (2n−2)(A+12)(B+1)(2^n-2)\dbinom{A+1}{2}(B+1)。

aa 为常数列 bb 非常数列

同理，贡献为 (2m−2)(B+12)(A+1)(2^m-2)\dbinom{B+1}{2}(A+1)。

aa 和 bb 都非常数列

不妨令 ai≠aja_i\neq a_j，bk≠blb_k\neq b_l。
由 ai⊕bk≠aj⊕bk≠aj⊕bla_i\oplus b_k\neq a_j\oplus b_k\neq a_j\oplus b_l 可知，ai⊕bk=aj⊕bla_i\oplus b_k=a_j\oplus b_l，否则集合中将至少有 33 个元素。
上式也即 ai⊕aj⊕bk⊕bl=0a_i\oplus a_j\oplus b_k\oplus b_l=0。
不妨记 a1a^1 和 a2a^2 为 aa 中两个不同元素，同理记 b1b^1 和 b2b^2。
我们即要统计元素对 (a1,a2,b1,b2)(a^1,a^2,b^1,b^2) 的个数，满足：
  • a1≠a2a^1\neq a^2，b1≠b2b^1\neq b^2。
  • a1,a2∈[0,A]a^1,a^2\in[0,A]，b1,b2∈[0,B]b^1,b^2\in [0,B]。
  • a1⊕a2⊕b1⊕b2=0a^1\oplus a^2\oplus b^1\oplus b^2=0。
发现可以进行数位dp。
设状态为 fi,0/1,0/1,0/1,0/1f_{i,0/1,0/1,0/1,0/1}，表示处理到从小到大第 ii 位，a1/a2/b1/b2a^1/a^2/b^1/b^2 是否在 A/a1/B/b1A/a^1/B/b^1 上界内的方案数。
对第一个 0/10/1 讨论转移方案，其余三个同理。
记 [a1][a^1] 为当前位 a1a^1 的取值，同理记 [A][A] 为当前位 AA 的取值。
  • 不在界内，即转移 fi,0,0/1,0/1,0/1f_{i,0,0/1,0/1,0/1}。
    因为没达到上界所以可以随便取，直接由 fi−1,0,0/1,0/1,0/1f_{i-1,0,0/1,0/1,0/1} 转移过来即可。
  • 在界内，即转移 fi,1,0/1,0/1,0/1f_{i,1,0/1,0/1,0/1}。
    此时乱取可能会导致情况不合法，考虑 [a1]=0/1[a^1]=0/1 和 [A]=0/1[A]=0/1。
    • [a1]=[A]=0/1[a^1]=[A]=0/1。
      此时该位置紧贴上界，故前一位不可任意取，需要在界内，即由 fi−1,1,0/1,0/1,0/1f_{i-1,1,0/1,0/1,0/1} 转移来。
    • [a1]=0<[A]=1[a^1]=0<[A]=1。
      此时该位置较小保证了小位随意取都可，即可由 fi−1,0,0/1,0/1,0/1f_{i-1,0,0/1,0/1,0/1} 转移来。
    • [a1]=1>[A]=0[a^1]=1>[A]=0。
      已出界，为 00。
记得转移前判断当前位异或和是否为 00，如此便可转移 ff。
然后发现，唉，我们现在是 a1≥a2a^1\ge a^2 与 b1≥b2b^1\ge b^2，我们还没剔除掉 a1≠a2a^1\neq a^2 和 b1≠b2b^1\neq b^2。
那我们还要再多加一层状态 0/10/1 在转移的时候顺便判断是否存在过 [a1]≠[a2][a^1]\neq[a^2] 和 [b1]≠[b2][b^1]\neq [b^2] 的状况。
我们提到了什么，“在转移的时候顺便”，那么我们用记忆化搜索来代替递推做数位dp的写法显然更为简洁。
在搜到最后如果发现所有 [a1]=[a2][a^1]=[a^2] 或 [b1]=[b2][b^1]=[b^2] 时则不计入即可。
最终贡献为 flog⁡2max⁡(A,B),1,1,1,1×(2n−2)(2m−2)f_{\log_2\max(A,B),1,1,1,1}\times (2^n-2)(2^m-2)。
最终四大类加和即可。

Time Complexity\text{Time Complexity}

计算快速幂有 O(log⁡n)O(\log n)，数位dp有 O(log⁡A)O(\log A)。
多测导致 O(t(log⁡n+log⁡A))O(t(\log n+\log A))。
虽说这个看起来很小但是实际上常数极大。
我们dp的状态数为 24log⁡A2^4\log A，每次转移有 242^4 项。
则实际上有约 28=2562^8=256 的常数。

Space Comlexity\text{Space Comlexity}

存储dp状态有 O(log⁡A)O(\log A)，但是与时间复杂度一样，有巨大常数，约 24=162^4=16。

Tips\text{Tips}

个人由于调用了不明内存导致调试时出现诡异现象，希望大家不会出现神秘段错误。

Code\text{Code}

CPP
inline void init(){
	for(re x=0;x<=M;++x)
		for(re i=0;i<=1;++i)
			for(re j=0;j<=1;++j)
				for(re k=0;k<=1;++k)
					for(re l=0;l<=1;++l) f[x][i][j][k][l]=-1;
}

int dfs(int x,int a1,int a2,int b1,int b2,int op){
	if(x==-1) return op;
	if(f[x][a1][a2][b1][b2]!=-1) return f[x][a1][a2][b1][b2];
	f[x][a1][a2][b1][b2]=0; 
	for(re i=0;i<=(a1?((A>>x)&1):1);++i)
		for(re j=0;j<=(a2?i:1);++j)
			for(re k=0;k<=(b1?((B>>x)&1):1);++k)
				for(re l=0;l<=(b2?k:1);++l) 
					if(i^j^k^l==0) f[x][a1][a2][b1][b2]=(f[x][a1][a2][b1][b2]+dfs(x-1,a1&(i==((A>>x)&1)),a2&(j==i),b1&(k==((B>>x)&1)),b2&(l==k),op|(i^j)))%mod;
	return f[x][a1][a2][b1][b2];
}

// ---------- dp ---------- //

int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
//	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	rd(t);
	while(t--){
		rd(n);rd(m);rd(A);rd(B);int tmp=max(A,B);M=0;
		while(tmp>>=1) ++M;init();
		ans=1ll*(A+1)*(B+1)%mod;
		ans=(ans+1ll*(pw(2,n)-2+mod)%mod*(A+1)%mod*A%mod*inv2%mod*(B+1)%mod)%mod;
		ans=(ans+1ll*(pw(2,m)-2+mod)%mod*(B+1)%mod*B%mod*inv2%mod*(A+1)%mod)%mod;
		ans=(ans+1ll*dfs(M,1,1,1,1,0)*(pw(2,n)-2+mod)%mod*(pw(2,m)-2+mod)%mod)%mod;
		wr(ans);puts("");
	}
	return 0;
}

// ---------- Main ---------- //

评论

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

正在加载评论...