CF1336E2 Chiori and Doll Picking 求一个线性基出来,求一下线性基可以表出多少数就好了。那么有一种简单暴力:直接枚举。加上折半搜索就可以过弱化版,不加折半搜索的复杂度是$O(2^r)$的。 还可以构造另一种算法:考虑令$f_{i,j}=f_{i-1,j}+f_{i-1,j \oplus A_i}$,那么构造序列$y$,使得$y_{i,0}=y_{i,a_i}=1,y_{i,j}=0$,那么答案就是$\prod y_i$。 那么考虑${\rm FWT}(y_i)_k$,它的值是$1+(-1)^{A_i \And w}$。那么$\Gamma_k = 2^n[ \forall i, A_i \And k \equiv 0 \pmod 2]$。 最终结果就是$f_i=\frac{1}{2^r} \sum_{j} \Gamma_j (-1)^{i \And j} $。 考虑计算答案$g$,$g_c=\sum_{s=c}f_s=\frac{1}{2^m} \sum_{t} \Gamma_t \sum_{s=c} (-1)^{s \And t}$ 后面这个$\sum$可以用组合数计算。确定了$t$,考虑$t=x$,那么钦定$x$中有$i$个产生贡献,剩下的$m-x$个位置一定是$0$,就可以确定$s$。$\sum_{i}\binom{x}{i}\binom{m-x}{c-i}(-1)^i$ 可以发现这个式子和$t$是什么无关,只和$t$有关。 那么问题就变成了求$\sum_{t=c} \Gamma_t$ 考虑什么时候$\Gamma_k$有值,即每一位,都有$A_i \And k \equiv 0 \pmod p$。 把$A_i \And k$写成矩阵,则每一行的和都为$0$。 与操作其实就是选其中的一些列,所以问题就变成了选一些列,使得和为$0$。 那么把线性基消成最简行阶梯矩阵,考虑在右边钦定一些列,那么存在唯一的方案,从左边的单位矩阵中选列,使它们的异或和为$0$。暴力枚举右边即可。复杂度$O(2^{m-r})$ 之后有一些细节,有关线性基的,新的线性基长什么样子。直接从题解里找图了,B就是:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 #include <bits/stdc++.h> using std::cerr;using std::endl;const int N = 60 , P = 998244353 ;inline long long fpow (long long x, int y) { if (y < 0 ) return fpow (fpow (x, -y), P - 2 ); long long ret = 1 ; for ( ; y; y >>= 1 , x = x * x % P) if (y & 1 ) ret = ret * x % P; return ret; } int n, m, rank;long long C[N][N];long long lb[N], nlb[N];long long p[N];inline void insert (long long x) { for (int i = m; ~i; --i) { if (x & (1ll << i)) { if (!lb[i]) { lb[i] = x; break ; } else x ^= lb[i]; } } } void dfs (long long s, int pos) { if (pos == rank) ++p[__builtin_popcountll(s)]; else { dfs (s, pos + 1 ); dfs (s ^ lb[pos], pos + 1 ); } } int main () { std::ios::sync_with_stdio (0 ); std::cin.tie (0 ); std::cin >> n >> m; for (int i = 1 ; i <= n; ++i) { long long x; std::cin >> x; insert (x); } for (int i = 0 ; i < m; ++i) { if (!lb[i]) continue ; for (int j = 0 ; j < i; ++j) if (lb[i] & (1ll << j)) lb[i] ^= lb[j]; for (int j = 0 ; j < m; ++j) if (!lb[j]) nlb[rank] = (nlb[rank] << 1 ) ((lb[i] >> j) & 1 ); nlb[rank] = 1ll << (m - rank - 1 ); ++rank; } for (int i = 0 ; i < rank; ++i) lb[i] = nlb[i], nlb[i] = 0 ; for (int i = rank; i < N; ++i) lb[i] = 0 , nlb[i] = 0 ; if (rank <= 26 ) { dfs (0 , 0 ); for (int i = 0 ; i <= m; ++i) { long long ans = p[i] * fpow (2 , n - rank) % P; std::cout << ans << " " ; } } else { rank = m - rank; for (int i = 0 ; i < rank; ++i) { for (int j = 0 ; j < m - rank; ++j) if (lb[j] & (1ll << i)) nlb[i] = 1ll << j; nlb[i] = 1ll << (m - i - 1 ); } std::swap (lb, nlb); dfs (0 , 0 ); for (int i = C[0 ][0 ] = C[1 ][0 ] = 1 ; i + 1 < N; ++i, C[i][0 ] = 1 ) for (int j = 1 ; j <= i; ++j) C[i][j] = (C[i - 1 ][j - 1 ] + C[i - 1 ][j]) % P; for (int i = 0 ; i <= m; ++i) { long long ans = 0 ; for (int j = 0 ; j <= m; ++j) { long long tmp = 0 ; for (int k = 0 ; k <= i; ++k) tmp = (tmp + (k & 1 ? P - 1 : 1 ) * C[j][k] % P * C[m - j][i - k]) % P; ans = (ans + tmp * p[j]) % P; } ans = ans * fpow (2 , n - m) % P; std::cout << ans << " " ; } } std::cout << std::endl; return 0 ; }