[ARC222E] XOR Matching

Genius_Star · 2026-09-08 21:41:15 · 题解

或许更好的阅读体验。

思路：

设 cnt_i 表示 a 中 i 的数量，那么显然：

这是显然的，因为 i 只能和 i \oplus x 配对，所以显然只能取两者数量较小的那个，注意 x = 0 的时候需要特判，因为此时是 \lfloor \frac{cnt_i}{2} \rfloor。

然后推式子（其中 c_i 是 cnt 排序后的结果，然后 p_i 是 c_i 原来是 cnt_{p_i} 排序过来的）：

于是本质上只需要对每个 i，算出 \sum_{j > i} 10^{p_i \oplus p_j} 即可，显然你发现它等价于强制在线修改算异或卷积，即（设 h_i 表示是否有 p_j 等于 i）：

即考虑 \{10^i\} 和 \{h\} 的异或卷积的第 p_i 位，就是 i 的答案，我们要支持的是单点修改 h，于是朴素 poly 做法肯定没有，于是直接根号分治，有值的 p 只有 n 个，设块长为 B，每经过 B 位就先 FWT 暴力卷一次，然后每次查询 i 答案就是 ans_{p_i} 再暴力遍历它后面最多 B 个。

复杂度是 O(\frac{n}{B} 2^m m + n B) \ge O(n \cdot 2^{\frac{m}{2}} \sqrt m)，可以通过。

轻微卡常。

完整代码：

#include<bits/stdc++.h>
#define fi first
#define se second
#define lowbit(x) (x) & (-(x))
#define popcnt(x) __builtin_popcount(x)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int N = 1.05e6 + 10, mod = 998244353;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
          f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
      write(x / 10);
    putchar(x % 10 + '0');
}
inline int add(int x, int y){
    return (x + y >= mod) ? (x + y - mod) : (x + y);
}
inline void getadd(int &x, int y){
    x = (x + y >= mod) ? (x + y - mod) : (x + y);
}
inline int dec(int x, int y){
    return (x < y) ? (x - y + mod) : (x - y);
}
inline void getdec(int &x, int y){
    x = (x < y) ? (x - y + mod) : (x - y);
}
namespace FWT{
    const int inv2 = (mod + 1) >> 1;
    inline void FWT_xor(int *A, int n){
        for(int i = 1; i < n; i <<= 1){
            for(int j = 0; j < n; j += (i << 1)){
                for(int k = 0; k < i; ++k){
                    int x = A[j + k], y = A[i + j + k];
                    A[j + k] = add(x, y);
                    A[i + j + k] = dec(x, y);
                }
            }
        }
    }
    inline void IFWT_xor(int *A, int n){
        for(int i = 1; i < n; i <<= 1){
            for(int j = 0; j < n; j += (i << 1)){
                for(int k = 0; k < i; ++k){
                    int x = A[j + k], y = A[i + j + k];
                    A[j + k] = 1ll * add(x, y) * inv2 % mod;
                    A[i + j + k] = 1ll * dec(x, y) * inv2 % mod;
                }
            }
        }
    }
};
struct Node{
    int cnt, p;
    inline bool operator<(const Node&rhs)const{
        return cnt > rhs.cnt;
    }
}A[N];
int n, m, lim, x, ans, B, lst;
int poww[N], ppow[N], h[N], hh[N], Ans[N];
inline void init(){
    poww[0] = ppow[0] = 1;
    for(int i = 1; i < N; ++i)
      ppow[i] = poww[i] = 10ll * poww[i - 1] % mod;
}
int main(){
    init();
    n = read(), m = read();
    lim = (1 << m);
    B = sqrt(lim * m) + 1;
    for(int i = 0; i < lim; ++i)
      A[i].p = i;
    while(n--){
        x = read();
        ++A[x].cnt;
    }
    int cnt = 0;
    for(int i = 0; i < lim; ++i)
      if(A[i].cnt)
        A[cnt++] = A[i];
    stable_sort(A, A + cnt);
    FWT::FWT_xor(ppow, lim);
    for(int i = 0; i < cnt; ++i){
        if(i % B == 0 && i){
            for(int x = 0; x < lim; ++x)
              hh[x] = h[x];
            FWT::FWT_xor(hh, lim); 
            for(int x = 0; x < lim; ++x)
              Ans[x] = 1ll * hh[x] * ppow[x] % mod;
            FWT::IFWT_xor(Ans, lim);
            lst = i;
        }
        getadd(ans, (A[i].cnt) >> 1);
        int sum = Ans[A[i].p];
        for(int j = lst; j < i; ++j)
          getadd(sum, poww[A[i].p ^ A[j].p]);
        // cerr << i << ' ' << sum << ' ' << lst << '\n';
        getadd(ans, 1ll * A[i].cnt * sum % mod);
        h[A[i].p] = 1;
    }
    write(ans);
    return 0;
}