【题解】CF1336E Chiori and Doll Picking

题目链接:CF1336E Chiori and Doll Picking

题意:

给定长度为 $n$ 的序列 $\{a_n\}$,$\forall i\in [1,n],\ a_i\in[0,2^m)$。

对 $c\in[0,m]$,计算有多少子序列的异或和的 $\text{popcount}=c$。

$1\le n\le 2\times 10^5,0\le m\le 53$。

看了一年 终于看懂了

首先,对于子序列的异或和这种操作,让我们联想到线性基。将一个整数看作 $\mathbb{F}_2$ 上的 $m$ 维向量,设 $V=\text{span}(a_1,a_2,\cdots,a_n)$,即序列中元素张出的向量空间,$k=\dim V$,即线性基的大小。

我们知道,对于任意 $x\in V$,都有恰好 $2^{n-k}$ 种方式通过序列中的元素异或来得到他。于是我们可以将问题转变为在线性基上计算答案,最后将答案 $\times 2^{n-k}$。

对线性基大小进行讨论。

当 $k\le 26$ 的时候,我们可以 $\mathcal{O}(2^{k})$ 枚举线性基中每个元素是否被选择。

而在 $k>26$ 的时候,我们希望得到一个 $\mathcal{O}(2^{m-k})$ 的算法,将两个算法结合得到一个 $\mathcal{O}(2^{\frac{m}{2}})$ 的算法。设:

$$ A_i=[i\in V] $$

$$ F^{(c)}_i=[\text{popcount}(i)=c] $$

则我们需要的应该是:

$$ \text{Ans}_c=\sum_{i=0}^{2^m-1} A_i F^{(c)}_i $$

即我既要能被张出,又要满足 $\text{popcount}$ 为定值 $c$。可以写作:

$$ \sum_{i=0}^{2^m-1} A_i\sum_{j=0}^{2^m-1} F^{(c)}_j [i=j] $$

将其写成异或卷积的形式,$i=j\iff i\oplus j=0$,于是所求即为:

$$ (A*F^{(c)})_0 $$

其中 $*$ 表示异或卷积。我们令 $\langle i,j\rangle=\text{popcount}(i \text{ and }j)\bmod 2$,即 $i,j$ 按位与的二进制位下 $1$ 的个数奇偶性。由于已经转化为异或卷积的形式,所以不妨考虑 $\text{FWT}(A)$ 与 $\text{FWT}(F^{(c)})$。

首先考虑 $\hat F^{(c)} =\text{FWT}(F^{(c)})$,他可以表示为:

$$ \hat F^{(c)}_i=\sum_{\text{popcount(j)=c}} (-1)^{\langle i, j\rangle} $$

令 $\text{popcount}(i)=a$,枚举 $b=\text{popcount}(i \text{ and }j)$,可以表示为:

$$ \hat F^{(c)}_i=\sum_{\text{popcount(j)=c}} (-1)^{\langle i, j\rangle}=\sum_{b=0}^m (-1)^b \binom{m-a}{c-b}\binom{a}{b} $$

注意到其值只与 $a,c$ 相关,设其为 $f(a,c)$。接下来考虑 $\hat A=\text{FWT}(A)$,可以表示为:

$$ \hat A_i=\sum_{j\in V}(-1)^{\langle i,j\rangle} $$

给出如下结论:

对于任意 $i\in[0,2^m)$,有 $\hat A_i\in\{0, 2^k\}$。

证明:

首先,一个事实是:$\langle a,c\rangle\oplus \langle b,c\rangle=\langle a\oplus b, c\rangle$。对于 $\forall x\in V$,在枚举的元素 $j$ 在遍历 $V$ 中所有元素的时候,$j\oplus x$ 也在遍历 $V$ 中所有元素。因此如果 $\exists j\in V$,$\langle i, j\rangle=1$,则 $\langle i,j\oplus x\rangle=0$,于是上述 $\hat A_i$ 中 $\pm 1$ 贡献抵消,和为 $0$。

如果 $\forall j\in V, \langle i,j\rangle=0$,则 $\hat A_i = 2^k$。

注意到这是一个齐次线性方程组,因此我们只需要找到一组基础解系,这些向量张出的向量空间中每个元素都满足 $\hat A_i=2^k$。设原线性基消元之后为 $M$,则 $M$ 可以表示为:

$$ M=\begin{bmatrix} E_k & X \end{bmatrix} $$

可以发现,$\begin{bmatrix} X\\E_{m-k}\end{bmatrix}$ 的列向量构成基础解系(可以验证两两按位与后 $1$ 的个数为偶数)。由于这里有 $m-k$ 个向量,所以我们可以在 $\mathcal{O}(2^{m-k})$ 的时间内,找到所有 $\hat A_i=2^k$ 的位置 $i$。

于是,我们所求的答案:

$$ \text{Ans}_c=\sum_{i=0}^{2^m-1} A_i F^{(c)}_i=(A*F^{(c)})_0=\dfrac{1}{2^{m}}\sum_{i=0}^{2^m-1} \hat A_i\hat F^{(c)}_i $$

$$ =\dfrac{1}{2^m}\sum_{a=0}^m 2^k\text{cnt}_a\times f(a,c) $$

其中 $\text{cnt}_a$ 表示 $\hat A_i =2^k$ 的 $i$ 中,$\text{popcount}(i)=a$ 的位置个数。

这样,我们就得到了一个神奇的 $\mathcal{O}(2^{m-k})$ 做法。结合对线性基内元素搜索的暴力,可以得到 $\mathcal{O}(2^{\frac{m}{2}})$ 的时间复杂度。

//Code By CXY07 - It's My Fiesta.
#include<bits/stdc++.h>
using namespace std;

//#define FILE
#define int long long
#define randint(l, r) (rand() % ((r) - (l) + 1) + (l))
#define abs(x) ((x) < 0 ? (-(x)) : (x))
#define popc(x) __builtin_popcountll(x)
#define inv(x) qpow((x), mod - 2)
#define lowbit(x) ((x) & (-(x)))
#define ull unsigned long long
#define pii pair<int, int>
#define LL long long
#define mp make_pair
#define pb push_back
#define scd second
#define vec vector
#define fst first
#define endl '\n'
#define y1 _y1

const int MAXN = 2e5 + 10;
const int MAXD = 60;
const int INF = 2e9;
const double eps = 1e-6;
const double PI = acos(-1);
//const int mod = 1e9 + 7;
const int mod = 998244353;
//const int G = 3;
//const int base = 131;

int n, m, k, tot;
int a[MAXN], d[MAXD], b[MAXD], cnt[MAXD], Ans[MAXD], s[MAXD];
int f[MAXD][MAXD], C[MAXD][MAXD];

template<typename T> inline bool read(T &a) {
    a = 0; char c = getchar(); int f = 1;
    while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); }
    while(c >= '0' && c <= '9') { a = a * 10 + (c ^ 48); c = getchar(); }
    return a *= f, true;
}

template<typename A, typename ...B>
inline bool read(A &x, B &...y) { return read(x) && read(y...); }

void Insert(int x) {
    for(int i = m - 1; ~i; --i) {
        if(!((x >> i) & 1)) continue;
        if(!d[i]) return d[i] = x, ++k, void();
        x ^= d[i];
    }
}

int qpow(int x, int b) {
    int res = 1; if(b < 0) b += mod - 1;
    for(; b; b >>= 1, (x *= x) %= mod) if(b & 1) (res *= x) %= mod;
    return res;
}

void DFS(int x, int S) {
    if(x > tot) return ++cnt[popc(S)], void();
    DFS(x + 1, S);
    if(s[x]) DFS(x + 1, S ^ s[x]);
}

signed main () {
#ifdef FILE
    freopen("CF1336E2.in", "r", stdin);
    freopen("CF1336E2.out", "w", stdout);
#endif
    read(n), read(m);
    for(int i = 0; i < MAXD; ++i) {
        C[i][0] = 1;
        for(int j = 1; j <= i; ++j)
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
    }
    for(int i = 1; i <= n; ++i) read(a[i]), Insert(a[i]);
    if(k <= 26) {
        for(int i = 0; i <= m; ++i) if(d[i]) s[++tot] = d[i];
        DFS(0, 0);
        for(int i = 0; i <= m; ++i) Ans[i] = cnt[i];
    } else {
        for(int i = m - 1; ~i; --i)
            for(int j = 0; j < m; ++j)
                if(i != j && (d[j] >> i) & 1) d[j] ^= d[i];
        for(int i = 0; i < m; ++i) {
            if(d[i]) continue;
            b[i] = (1ll << i); 
            for(int j = 0; j < m; ++j) if((d[j] >> i) & 1) b[i] |= (1ll << j);
        } 
        for(int i = 0; i <= m; ++i) if(b[i]) s[++tot] = b[i];
        for(int a = 0; a <= m; ++a)
            for(int c = 0; c <= m; ++c)
                for(int b = 0, opt = 1; b <= c; ++b) {
                    (f[a][c] += C[m - a][c - b] * C[a][b] % mod * opt) %= mod;
                    opt = (mod - opt) % mod;
                }
        DFS(0, 0);
        for(int i = 0; i <= m; ++i) {
            for(int j = 0; j <= m; ++j) (Ans[i] += cnt[j] * f[j][i]) %= mod;
            Ans[i] = Ans[i] * qpow(2, k - m) % mod;
        }
    }
    for(int i = 0; i <= m; ++i) Ans[i] = Ans[i] * qpow(2, n - k) % mod;
    for(int i = 0; i <= m; ++i) printf("%lld ", Ans[i]);
    return 0;
}
添加新评论