cf1336e

https://codeforces.ml/contest/1336/problem/E2

https://codeforces.ml/blog/entry/76099

题解非常详尽，来为自己补充一下题解。

$1.$长度为$k$的线性基每种组合的出现次数都是$2^{n-k}$。这第一步我就没想到。考虑前$k$个数已经能形成$2^k$个数了，那么我新添一个数，答案必然乘$2$，因为异或的数不同结果不同。

$2.$algorithm $2$讲述了$m\leq 35$时候的$dp$。其实，用当时学Menci的线性基插入方法，他所要求的线性基已经自动消元好了。

inline void ins(int x) {
  if (!x) return;
  for (int i = 29; i >= 0; i--) {
    if (!(x >> i & 1)) continue;
    if (b[i]) { x ^= b[i]; continue; }
    rep(j, i) if (x >> j & 1) x ^= b[j];
    for (int j = i + 1; j < 30; j++) if (b[j] >> i & 1) b[j] ^= x;
    b[i] = x;
    return;
  }
}

$3.$algorithm $3$里面初始的诀窍是非常强的。

$S(A)$表示可以由线性基组成的所有数。

令$a_i=[i \in S(A)],f_i^c=[popcount(i)=c],res_i=[x^0]a \oplus f^c$。

sundz说他只要会这个就能吊打tourist了。足见这个的重要。

$4.$下面就是研究如何快速$fwt$和$ifwt$，希望总复杂度在$O(2^{m-k})$。

$5.$Lemma $1,2,3,4$都好神仙，sundz全秒了！

$6.p_c = \dfrac{1}{2^m}\sum\limits_{d=0}^{m} 2^k q_d w_d^c = \dfrac{1}{2^{m-k}}\sum\limits_{d=0}^{m} q_d w_d^c$

也就是$f_0=\frac{1}{2^m}\sum\limits_{i=0}^{2^m - 1}fwt(f)_i$，解释看下面。

这题结束了，让我们来回忆一下fwt吧！

要求我们构造一种运算，使得

$FWT(a)_i*FWT(b)_i=FWT(c)_i$

$\sum\limits_{x=0}^{2^m-1}a_xf_{i,x} *\sum\limits_{y=0}^{2^m-1}b_yf_{i,y}=\sum\limits_{z=0}^{2^m-1}c_zf_{i,z}$

$f_{i,x}*f_{i,y}=f(i,x \oplus y)$

尽量让他们解的值不同。

https://www.cnblogs.com/y-clever/p/6875743.html

https://www.cnblogs.com/y-clever/p/6979925.html

也就是说，只要通过解方程，就可以构造任意位运算的fwt！

而且如果实在忘记怎么写，也可以自己手动构造，然后写成这样：

void FWT_Or(int *A, int len) {
  if (len == 1) return;
  int len2 = len >> 1;
  FWT_Or(A, len2);
  FWT_Or(A + len2, len2);
  for (int i = 0; i < len2; ++i)
    A[i + len2] += A[i];
}
void IFWT_Or(int *A, int len) {
  if (len == 1) return;
  int len2 = len >> 1;
  for (int i = 0; i < len2; ++i)
    A[i + len2] -= A[i];
  IFWT_Or(A, len2);
  IFWT_Or(A + len2, len2);
}

这也可以解释$6$，每层递归都是$/=2$。

做题的时候又忘了，再记一遍。