快速沃尔什变换(FWT)是一种处理下标为位运算的卷积的算法。

形如以下形式

$$ C[i]=\sum_{j\oplus k=i}A[j]B[k] $$

其中 $\oplus$ 属于位运算运算符,常见的例如:与(and)、或(or)、异或(xor)。

参考 FFT 的做法,将原多项式变换为可以进行点积的 $n$ 维向量的形式。

考虑构造多项式 $\text A$ 变化后的 $n$ 维向量 $\text{fwt(A)}$ 为

$$ fwt(A)[i]=\sum_{j\&i=i}A[j] $$

这样构造满足,变换后的两个向量点积式是下标为与的卷积的多项式的变换后的向量式,即

$$ fwt(A\times B)=fwt(A)\cdot fwt(B) $$

$$ (\sum_{j\&i=i}A[j])\cdot(\sum_{k\&i=i}B[k]) $$

由 $[j\&i=i]\times [k\&i=i]$ 等价于 $[j\&k\&i=i]$,可以将其求和合并

$$ \sum_{(j\&k)\&i=i}A[j]B[k] $$

就是卷积后多项式的变换出的向量。

这样就证明了变换后的向量卷积即为目标变换的向量。

现在需要考虑在 $\mathcal O(n\log n)$ 的时间内构造出变换后的向量。

构造方式如下:

我们令 $\text A_0$ 为长度为 $2^n$ 的多项式 $\text A$ 其中下标二进制最高为 $0$ 的元素 ,即前 $2^{n-1}$ 个,而 $\text A_1$ 为后 $2^{n-1}$ 个。

$$ fwt(A)=merge(fwt(A_0)+fwt(A_1),fwt(A_1)) $$

其中 $merge$ 为将两个向量拼接起来。

其意义为下标最高位为 $1$ 的元素和 $0$ 与(and)运算后,会对下标最高位为 $0$ 的元素有贡献。

那么我们就考虑用类似 FFT 的迭代来求解变换后的向量。具体地,枚举区间的长度,等价于递归的深度,然后对于每一个区间内的元素都一定是后面的元素会对前面的元素有贡献。

void fwtAnd(int* a, int n) {
  for (int len = 1; len < n; len <<= 1)
    for (int i = 0; i < n; i += (len << 1))
      for (int j = 0; j < len; j++)
        a[i + j] = (a[i + j] + a[i + j + len]);
}

代码中 len 枚举的是半个区间的长度。

考虑怎样逆变换(IFWT),也就是已知变换后的向量 $A$,还原出变换前的多项式。

$$ A=merge(A_0-A_1,A_1) $$

可以用方程思想来解决这个问题,可以自行思考。

void fwtAnd(int* a, int n) {
  for (int len = 1; len < n; len <<= 1)
    for (int i = 0; i < n; i += (len << 1))
      for (int j = 0; j < len; j++)
        a[i + j] = (a[i + j] - a[i + j + len]);
}

可以将其合并成一份代码。

或和与的处理方式相似,就不再赘述。

void fwtOr(int* a, int n, int type = 1) {
  for (int len = 1; len < n; len <<= 1)
    for (int i = 0; i < n; i += (len << 1))
      for (int j = 0; j < len; j++)
        a[i + j + len] = (a[i + j + len] + a[i + j] * type % p + p) % p;
}

异或

构造方式为下标和 $i$ 与运算后的二进制 $1$ 的个数的奇偶性。

太麻烦了,懒得讲了,之后有时间在补起来。

void fwtXor(int* a, int n, int type = 1) {
  for (int len = 1; len < n; len <<= 1)
    for (int i = 0; i < n; i += (len << 1))
      for (int j = 0; j < len; j++) {
        int x = a[i + j], y = a[i + j + len];
        a[i + j] = (x + y) % p;
        a[i + j + len] = (x - y) % p;
        if (a[i + j + len] < 0)
          a[i + j + len] += p;
        if (type == -1) {
          a[i + j] = 1ll * a[i + j] * inv2 % p;
          a[i + j + len] = 1ll * a[i + j + len] * inv2 % p;
        }
      }
}
最后修改:2020 年 09 月 05 日 04 : 31 PM
如果觉得我的文章对你有用,请随意赞赏