CF1336E2 Chiori and Doll Picking

题意：给定 $n$ 个数 $a_{i}$ ，每个数小于 $2^{m}$ ，问对于每个 $i \in [0, m]$ 求出任意选出一些数使得异或和 __builtin_popcount 为 $i$ 的方案数。 $n \leq 2 \times 10^{5}$ ， $m \leq 53$ 。

容易发现建出线性基过后相当于是对线性基求剩下的问题。假设线性基大小为 $k$ 。

暴力是好做的，直接 $O (2^{k})$ 枚举即可，不多赘述。

对于 $k$ 比较大的，首先我们有一个暴力 DP 思路：由于线性基的性质，每一个数恰好对应一位，我们可以通过消元使得只剩每一个数只有他自己该位是 1。那么剩下的 $m - k$ 位可以直接 DP，记 $f (i, s)$ 表示选了 $i$ 个数，剩下 $m - k$ 状态为 $s$ 的方案数。于是可以做到 $O (2^{m - k} m^{2})$ ，还是不够优秀。

容易发现 $m \leq 53$ 要求我们有 $O (2^{k})$ 和 $O (2^{m - k})$ 两种做法，所以我们尝试寻找另外的方案。

考虑使用集合幂级数，令 $F_{c} (x) = \sum_{i} [| i | = c] x^{i}$ ， $| s |$ 表示 __builtin_popcount。将所有线性基能生成的数塞到一个集合幂级数，令为 $A$ ，那么 $c$ 的答案就是 $(A \times F_{c}) [x^{0}]$ 。

考虑首先对 $A$ 做 FWT。写一个暴力可以观察到这样几个性质：

$FWT (A)$ 只有 $2^{k}$ 和 0 两种取值。假设当前位置为 $x$ ，我们考虑从线性基中任选数，如果存在一个满足 $| x \cap a_{i} |$ 为奇数的话，那么选他和不选他的贡献就是相反的，所以最后就是 0。否则就是 $2^{k}$ 。
假设非 0 位置构成集合为 $B$ ， $B$ 是一个线性基的张集并且线性基大小为 $m - k$ 。容易发现对于任意一个 $a_{i}$ ， $| x \cap a_{i} | + | y \cap a_{i} |$ 和 $| (x \oplus y) \cap a_{i} |$ 奇偶性相同。那么说明任意 $x, y \in B$ 都有 $x \oplus y \in B$ ，也就说明 $B$ 是线性基张集。大小我们可以考虑由于 $2^{k} B = FWT(A)$ ，我们对两边同时 iFWT 可以得到 $2^{k} iFWT (B) = A$ 。观察 $A$ 包含 0，所以 $2^{k - m} | B | = 1$ ，也就是 $| B | = 2^{m - k}$ 。
$B$ 线性基关键位是 $A$ 中非关键位，并且把 $A, B$ 写在一个 01 矩阵 $M$ 上满足 $i$ 行的第 $i$ 位为 1。可以证明 $M = M^{T}$ 。不会证，可以观察一下（

那么我们找到 $B$ 就相当是找到了 $FWT (A)$ ，我们把线性基翻转一下就可以得到了 $B$ 的线性基。

下面考虑如何求出 $FWT (F_{c})$ 。容易发现最后每一个位置的答案只和 __builtin_popcount 有关。考虑 $c$ 向一个 $i \in [0, m]$ 的贡献权值，容易发现可以枚举相交部分为 $j$ ，那么贡献为 $(- 1)^{j} (\binom{i}{j}) (\binom{m - i}{c - j})$ 。直接计算是 $O (m^{3})$ 的，可以接受。

最后我们合并的时候还是发现最后答案只和 B 所有数的 __builtin_popcount 有关，求出张集过后直接贡献到对应位置即可。后面求 0 项值就是求所有和。注意要 iFWT 要除以 $2^{m}$ 。但是线性基只有 $k$ 大小，原来是 $n$ 大小，乘上一个 $2^{n - k}$ 即可。所以可以做到 $O (2^{m - k})$ 。

平衡一下可以得到 $O (2^{\frac{m}{2}} + m^{3})$ ，可以通过。

void dfs(int pos, LL cur)
{
	if (!pos) return cnt[popcount(cur)] ++, void();
	dfs(pos - 1, cur), dfs(pos - 1, cur ^ tmp[pos]);
}

int main()
{
	int n;
	std::cin >> n >> m;
	for (int i = 1; i <= n; ++ i)
	{
		scanf("%lld", &x);
		for (int j = m - 1; ~j; -- j) {
			if (~x >> j & 1) continue;
			if (!a[j]) {
				a[j] = x;
				break;
			}
			x ^= a[j];
		}
	}
	int sz = 0;
	for (int i = 0; i < m; ++ i) sz += !!a[i];
	if (sz <= 26) {
		int t = 0;
		for (int i = 0; i < m; ++ i)
			if (a[i]) tmp[++ t] = a[i];
		dfs(sz, 0);
		for (int i = 0; i <= m; ++ i) std::cout << (LL) cnt[i] * qpow(2, n - sz) % Mod << ' ';
		std::cout << '\n';
		return 0;
	}
	for (int i = C[0][0] = 1; i < N; ++ i)
		for (int j = C[i][0] = 1; j <= i; ++ j)
			upd(C[i][j] = C[i - 1][j - 1], C[i - 1][j]);
	for (int i = 0; i <= m; ++ i)
		for (int j = 0; j <= m; ++ j)
			for (int k = 0; k <= i && k <= j; ++ k)
				if (~k & 1) upd(f[i][j], (LL) C[i][k] * C[m - i][j - k] % Mod);
				else upd(f[i][j], Mod - (LL) C[i][k] * C[m - i][j - k] % Mod);
	for (int i = m - 1; ~i; -- i) if (a[i])
		for (int j = i + 1; j < m; ++ j)
			if (a[j] >> i & 1) a[j] ^= a[i];
	for (int i = 0; i < m; ++ i)
		for (int j = 0; j < i; ++ j) {
			int x = a[i] >> j & 1, y = a[j] >> i & 1;
			if (x == y) continue;
			a[i] ^= (1LL << j), a[j] ^= (1LL << i);
		}
	int t = 0;
	for (int i = 0; i < m; ++ i)
		if (~a[i] >> i & 1) tmp[++ t] = a[i] | (1LL << i);
	dfs(t, 0);
	for (int i = 0; i <= m; ++ i) {
		int res = 0;
		for (int j = 0; j <= m; ++ j)
			upd(res, (LL) cnt[j] * f[j][i] % Mod * qpow(2, Mod - 1 + sz - m) % Mod);
		res = (LL) res * qpow(2, n - sz) % Mod;
		std::cout << res << ' ';
	}
	return 0;
}