CF1366E Chiori and Doll Picking
位运算和 __builtin 函数记得开 long long！！！！！
这题很厉害。
记 \(p(x) = \operatorname{popcount}(x)\)，\(\operatorname{span}(B)\) 表示 \(B\) 张成的线性空间。
首先有一个暴力的想法：找到每个能异或出来的数 \(x\)，然后统计到 \(p(x)\) 的答案中，然后可以联想到 P4869 的线性基的性质，先求出线性基 \(B\)，只用枚举线性空间中的所有数，暴力统计答案，最后乘一个 \(2^{n-|B|}\) 就有 \(O(2^m + nm)\) 的算法了。
所以这题的序列其实是没用的，就忘掉 \(n\) 这个东西，直接来看怎么和这个线性基玩耍。
首先 \(|B|\) 较小的情况是可以直接暴力的，现在来看 \(B\) 较大时怎么做。
考虑转化成卷积，设 \(F = \sum_k [k \in \operatorname{span}(B)] x^k\)，\(G_c = \sum_k [p(k) = c]x^k\)，有
用 FWT 的方法就是
这种题经常可以通过快速算 FWT 来加速，先考虑外面的 \(\operatorname{IFWT}\)，因为只用求一项，所以只用求出里面的每一项系数加起来乘 \(2^{-m}\) 就行了。
先解决比较简单的部分
转而枚举 \(|j \cap k|\) ，可得
这样就可以 \(O(m^2)\) 计算一类 \(c\) 的后半部分的贡献了。
现在再来考虑前面的部分。
这个式子看着很优美，但是没有头绪。
考虑反过来看待贡献，\(\operatorname{span}(B)\) 中的 \(j\) 对 \(k\) 的贡献为 \((-1)^{|j \cap k|}\)
如果把 \(|x \cap y|\) 当作 \(x\) 与 \(y\) 的内积，那么 \((-1)^{|x \cap y|} = 1\) 就当且仅当 \(x\) 与 \(y\) 正交！
所以如果能求出另一个线性空间，使得其中的向量与 \(\operatorname{span}(B)\) 中向量正交，那么至少这个线性空间内的系数都是 \(2^{|B|}\)！
但是这个结论仍然不够优秀，因为剩下的系数都还未知。
继续考虑线性空间的性质，注意到加法封闭性，所以对于一个确定的 \(k\) 而言满足 \(i + j = k\) 的 \((i, j)\)，恰有 \(|\operatorname{span}(B)|\) 对。
这意味着对于集合幂级数 \(F\), 有 \(F * F = F \times 2^{|B|}\)，意思就是 \(\operatorname{FWT}(F) \times \operatorname{FWT}(F) = \operatorname{FWT}(F) \times 2^{|B|}\)，也就是说 \(\operatorname{FWT}(F)\) 的系数只能为 \(\{0, 2^{B}\}\) 二者其一！
结合上面，我们知道，\(x_k\) 的系数为 \(2^{|B|}\) 当且仅当 \(k\) 在所谓的“另一个线性空间中”。所以只有“另一个线性空间”中的数会有 \(2^{|B|}\) 的贡献。因此求出另一个线性空间中 \(p(x) = c\) 的 \(x\) 的数量即可！
而这“另一个线性空间”的实质就是 \(B\) 的正交线性基 \(B^\perp\) 张成的线性空间！这样只需要求 \(B^\perp\) 就行了。
首先对 \(B\) 做高斯消元，使得其中关键位各自独立，然后对于每一个非关键位 \(i\)，我们希望这一维的基向量只涉及这一位和 \(B\) 中的关键位，那么第 \(j\) 位为 \(1\) 当且仅当 \(B\) 中关键位为 \(j\) 的向量的第 \(i\) 位为 \(1\)。不难发现这样构造出来的 \(B^\perp\) 满足条件！
于是，我们在 \(O(2^{\frac m2} + m^3 + nm)\) 的时间内解决了这道题。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
namespace IO {
#define isdigit(x) (x >= '0' && x <= '9')
template<typename T>
inline void read(T &x) {
x = 0; char ch = getchar(); int f = 0;
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
if(f) x = -x;
}
template<typename T>
inline void write(T x) {
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
#undef isdigit
}
using namespace IO;
const int N = 2e5 + 10;
const int M = 57;
const int P = 998244353;
const int inv2 = (P + 1) / 2;
inline void add(int &x, int y) {
(x += y) >= P ? x -= P : 0;
}
int n, m, k;
LL f[M], a[M], b[M];
int c[M][M];
int q[M];
void dfs(int j, LL x) {
if(j == k) ++q[__builtin_popcountll(x)];
else dfs(j + 1, x), dfs(j + 1, x ^ a[j]);
}
signed main() {
read(n), read(m);
for(int i = 1; i <= n; ++i) {
LL x; read(x);
for(int j = m - 1; j >= 0; --j)
if(x >> j & 1) {
if(!f[j]) {
f[j] = x, ++k;
break;
} else x ^= f[j];
}
}
if(k <= 27) {
k = 0;
for(int i = 0; i <= m; ++i)
if(f[i]) a[k++] = f[i];
dfs(0, 0);
int coe = 1;
for(int i = 1; i <= n - k; ++i)
add(coe, coe);
for(int i = 0; i <= m; ++i)
printf("%lld ",1ll * coe * q[i] % P);
} else {
for(int i = m - 1; i >= 0; --i)
for(int j = i - 1; j >= 0; --j)
if(f[i] >> j & 1) f[i] ^= f[j];
k = 0;
for(int i = m - 1; i >= 0; --i)
if(!f[i]) {
a[k] = 0;
for(int j = m - 1; j >= 0; --j)
if(f[j] >> i & 1) a[k] |= 1ll << j;
a[k++] |= 1ll << i;
}
dfs(0, 0);
for(int i = 0; i <= m; ++i)
c[i][0] = 1;
for(int i = 1; i <= m; ++i)
for(int j = 1; j <= m; ++j)
add(c[i][j] = c[i - 1][j - 1], c[i - 1][j]);
int w = 1;
for(int i = 1; i <= k; ++i)
w = 1ll * w * inv2 % P;
for(int i = 1; i <= n - m + k; ++i)
add(w, w);
for(int i = 0; i <= m; ++i) {
int ans = 0;
for(int d = 0; d <= m; ++d) {
int coe = 0;
for(int j = 0; j <= i; ++j) {
if(j & 1) add(coe, P - 1ll * c[d][j] * c[m - d][i - j] % P);
else add(coe, 1ll * c[d][j] * c[m - d][i - j] % P);
}
add(ans, 1ll * q[d] * coe % P);
}
ans = 1ll * ans * w % P;
printf("%d ",ans);
}
}
puts("");
return 0;
}