CF1336E2 Chiori and Doll Picking FWT线性基

发表于 更新于 分类于 阅读次数：

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;
}