CF2075E XOR Matrix 题解数位dp

Demoe · 2025-04-03 20:26:05 · 题解

\large\text{题目传送门}

\text{Description}

求整数数列 (a,b) 对数满足集合 \{a_i\oplus b_j\} 不超过 2 个元素。（其中 \oplus 代表位异或）
其中 a 长度为 n，值域为 [0,A]；b 长度为 m，值域为 [0,B]。
多测，答案对 998244353 取模。

\text{Solution}

显然若存在 a_i\ne a_j，则有 a_i\oplus b_k\neq a_j\oplus b_k。

而最终集合不超过 2 个元素，则可知整数数列 a 和 b 中也各自最多有 2 个不同的数值。

那么就分作四大类讨论：

a 和 b 都为常数列

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

a 非常数列 b 为常数列

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

a 为常数列 b 非常数列

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

a 和 b 都非常数列

不妨令 a_i\neq a_j，b_k\neq b_l。

由 a_i\oplus b_k\neq a_j\oplus b_k\neq a_j\oplus b_l 可知，a_i\oplus b_k=a_j\oplus b_l，否则集合中将至少有 3 个元素。

上式也即 a_i\oplus a_j\oplus b_k\oplus b_l=0。

不妨记 a^1 和 a^2 为 a 中两个不同元素，同理记 b^1 和 b^2。

我们即要统计元素对 (a^1,a^2,b^1,b^2) 的个数，满足：

发现可以进行数位dp。

设状态为 f_{i,0/1,0/1,0/1,0/1}，表示处理到从小到大第 i 位，a^1/a^2/b^1/b^2 是否在 A/a^1/B/b^1 上界内的方案数。

对第一个 0/1 讨论转移方案，其余三个同理。

记 [a^1] 为当前位 a^1 的取值，同理记 [A] 为当前位 A 的取值。

不在界内，即转移 f_{i,0,0/1,0/1,0/1}。

因为没达到上界所以可以随便取，直接由 f_{i-1,0,0/1,0/1,0/1} 转移过来即可。
在界内，即转移 f_{i,1,0/1,0/1,0/1}。

此时乱取可能会导致情况不合法，考虑 [a^1]=0/1 和 [A]=0/1。
此时该位置紧贴上界，故前一位不可任意取，需要在界内，即由 f_{i-1,1,0/1,0/1,0/1} 转移来。
此时该位置较小保证了小位随意取都可，即可由 f_{i-1,0,0/1,0/1,0/1} 转移来。
已出界，为 0。

记得转移前判断当前位异或和是否为 0，如此便可转移 f。

然后发现，唉，我们现在是 a^1\ge a^2 与 b^1\ge b^2，我们还没剔除掉 a^1\neq a^2 和 b^1\neq b^2。

那我们还要再多加一层状态 0/1 在转移的时候顺便判断是否存在过 [a^1]\neq[a^2] 和 [b^1]\neq [b^2] 的状况。

我们提到了什么，“在转移的时候顺便”，那么我们用记忆化搜索来代替递推做数位dp的写法显然更为简洁。

在搜到最后如果发现所有 [a^1]=[a^2] 或 [b^1]=[b^2] 时则不计入即可。

最终贡献为 f_{\log_2\max(A,B),1,1,1,1}\times (2^n-2)(2^m-2)。

最终四大类加和即可。

\text{Time Complexity}

计算快速幂有 O(\log n)，数位dp有 O(\log A)。

多测导致 O(t(\log n+\log A))。

虽说这个看起来很小但是实际上常数极大。

我们dp的状态数为 2^4\log A，每次转移有 2^4 项。

则实际上有约 2^8=256 的常数。

\text{Space Comlexity}

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

\text{Tips}

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

\text{Code}

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 ---------- //

CF2075E XOR Matrix 题解 数位dp