题解 GYM102331B Bitwise Xor

jiangly contest T3。

用 01-trie 优化 DP。

题意

给出长为 \(n\) 的序列 \(a\) 和 \(x\)，若一个 \(a\) 的长为 \(k\) 的子序列 \(b\) 满足对于 \(b_i \operatorname{xor} b_j \ge x(1\le i < j\le k)\)，则是合法的序列，求 \(a\) 的合法序列方案数。

\(1\le n\le 3\times 10^5,0\le a_i\le 2^{60}-1\)。

思路

\(b\) 的条件要求 \(b_i \operatorname{xor} b_j\) 的最小值大于等于 \(x\)，条件很严苛。

但是将 \(b\) 排序后，这个最小值只能出现在相邻两项的异或值。

于是我们只要保证相邻两项异或值大于等于 \(x\)。（考场上看错题的）

可以轻松的到 \(\mathcal O(n^2)\) 的 DP 转移方程： \[ f_i\leftarrow 1+\sum_{1\le j< i}[a_i \operatorname{xor} a_j\ge x]f_j \] 考虑从异或入手，可以想到 01-trie。

在 01-trie 上节点存子树权值和，每次查询符合条件的 \(\sum f_j\) 并插入 \(a_i\) 权值为 \(f_i\)。

如何查询？

我们令 \(a_i \operatorname{xor} a_j=x\)，在 trie 上 \(a_j\) 的这条路径上，对于从高到低每一位，设这一位 \(a_j\) 为 \(a\)，\(a_j\) 为 \(b\)，\(x\) 为 \(c\)。

如果 \(c\) 为 \(0\)，那么这一位可以为 \(1\)，加上 \(a \operatorname{xor} 1\) 的子树。

复杂度 \(\mathcal O(n\log a)\)。

代码

const int N = 3e5 + 9;
const int P = 998244353;
 
int n, tot;
LL k, ans;
LL a[N], sum[N*60], ch[N*60][2], f[N];
 
inline void insert(LL x, LL val) {
    int p = 1;
    for (int i = 61; ~i; --i) {
        int c = (x >> i) & 1;
        if (!ch[p][c]) ch[p][c] = ++tot;
        p = ch[p][c];
        (sum[p] += val) %= P;
    }
}
 
inline LL query(LL x) {
    int p = 1;
    LL res = 0;
    for (int i = 61; ~i; --i) {
        int c = (x >> i) & 1, d = (k >> i) & 1;
        if (!d) (res += sum[ch[p][c ^ 1]]) %= P;
        p = ch[p][c ^ d];
        if (!p) break;
    }
    (res += sum[p]) %= P;
    return res;
}
 
inline void main() {
    read(n), read(k);
    for (int i = 1; i <= n; ++i) read(a[i]);
    sort(a+1, a+n+1);
    
    tot = 1;
    for (int i = 1; i <= n; ++i) {
        f[i] = (query(a[i]) + 1) % P;
        insert(a[i], f[i]);
        (ans += f[i]) %= P;
    }
    printf("%lld\n", ans);
}