【题解】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;
}