fwt小记(FWT notes)

这是属于补锅计划的一部分。

那就直接进入正题。

理论基础

用于解决求解 \(A\oplus B\) 的方法,其中(\(\oplus\) 是二进制运算)

名字很高级 ,其实基本思想比较简单。

快速莫比乌斯/沃尔什变换 (FMT/FWT) 

假设有一个序列 \(A\) ,通过某种变换我们可以得到另一个序列 \(fwt[A]\) ,如果对于整个序列 \(A\) 复杂度为 \(O(n^2)\) 的计算可以等价于在 \(fwt[A]\) 中的 \(O(n)\) 的计算,那么只要这种变换的复杂度很低,那么整个过程的复杂度就降下来了。

比如卷积,两个函数的的卷积我们不好求,但我们可以用 \(O(n\log n)\) 的复杂度求出他的点值,而点值的运算等价于原函数的计算,那么整个FFT的复杂度就是 \(O(n\log n)\) 的。

具体去解释这个变换比较复杂,推荐先通过模板题题解区了解具体操作再来学习理论。

这里就挑其中的一些重点,省去了一些证明,全面的解释见这 。

  • FWT 是一个线性变换 ,即你可以理解为 \(A\) 是一个 \(n\) 维向量,变换是一个 \(n\times n\) 的矩阵 \(C\),\(fwt[A]_i=\sum\limits_{j=0}^{n-1} A_j C_{i,j}\) 。
  • 因为 \(\oplus\) 是二进制运算,所以我们可以把每一位分开考虑(按位拆半)。
    设 \(A_0\) 为幂级数下标首位为 \(0\) 的部分,类似地有 \(A_1\)。

    若 \(i_0=0\) ,则有 :
    \(fwt[A]_i=c(0,0)fwt[A_0]_i+c(0,1)fwt[A_1]_i\quad \big(i\in[0,n/2)\big)\)

    若 \(i_0=1\) ,则有 :
    \(fwt[A]_{i+(n/2)}=c(1,0)fwt[A_0]_i+c(1,1)fwt[A_1]_i\quad \big(i\in[0,n/2)\big)\)

    所以对于 \(C\) 矩阵来说,有用的只有 \(c([0,1],[0,1])\) 。

  • 若 \(i_0=0\) ,则有 :
    \(fwt[A]_i=c(0,0)fwt[A_0]_i+c(0,1)fwt[A_1]_i\quad \big(i\in[0,n/2)\big)\)
  • 若 \(i_0=1\) ,则有 :
    \(fwt[A]_{i+(n/2)}=c(1,0)fwt[A_0]_i+c(1,1)fwt[A_1]_i\quad \big(i\in[0,n/2)\big)\)
  • \(fwt[A]\) 变换回 \(A\) 就是通过 \(C\) 的逆矩阵得到,因为 \(A*C=fwt[A]\rightarrow fwt[A]*C^{-1}=A\) 。

模板

即求解 \(c_i=\sum\limits_{j|k=i} a_jb_k\) 。

  • 矩阵: \(\begin{bmatrix}1&0\\1&1\end{bmatrix}\) 。
    即 \(fwt[A]_i=fwt[A_0]_i\;\;fwt[A]_{i+(n/2)}=fwt[A_0]_i+fwt[A_1]_i\) 。
    \(c(i,j)=[i|j=i]\) 。
    含义:子集求和(高维前缀和)
  • 逆矩阵: \(\begin{bmatrix}1&0\\-1&1\end{bmatrix}\) 。
    即 \(fwt[A]_i=fwt[A_0]_i\;\;fwt[A]_{i+(n/2)}=-fwt[A_0]_i+fwt[A_1]_i\) 。
    含义:高维前缀差。

即求解 \(c_i=\sum\limits_{j\&k=i} a_jb_k\) 。

  • 矩阵: \(\begin{bmatrix}1&1\\0&1\end{bmatrix}\) 。
    即 \(fwt[A]_i=fwt[A_0]_i+fwt[A_1]_i\;\;fwt[A]_{i+(n/2)}=fwt[A_1]_i\) 。
    \(c(i,j)=[i\&j=i]\) 。
    含义:超集求和(高维后缀和)
  • 逆矩阵: \(\begin{bmatrix}1&-1\\0&1\end{bmatrix}\) 。
    即 \(fwt[A]_i=fwt[A_0]_i-fwt[A_1]_i\;\;fwt[A]_{i+(n/2)}=fwt[A_1]_i\) 。
    含义:高维后缀差。

异或

即求解 \(c_i=\sum\limits_{j\text{xor} k=i} a_jb_k\) 。

  • 矩阵: \(\begin{bmatrix}1&1\\1&-1\end{bmatrix}\) 。
    即 \(fwt[A]_i=fwt[A_0]_i+fwt[A_1]_i\;\;fwt[A]_{i+(n/2)}=fwt[A_1]_i-fwt[A_1]_i\) 。
    \(c(i,j)=(-1)^{|i\&j|}\) 。
    含义:不知道…
  • 逆矩阵: \(\begin{bmatrix}0.5&0.5\\0.5&-0.5\end{bmatrix}\) 。
    即 \(fwt[A]_i=\frac{1}{2}(fwt[A_0]_i+fwt[A_1]_i)\;\;fwt[A]_{i+(n/2)}=\frac{1}{2}(fwt[A_1]_i-fwt[A_1]_i)\) 。

代码,复杂度是 \(O(n\log n)\) 的。

例题

  • CF662C Binary Table

因为 \(n\) 很小,我们可以暴力考虑每一行翻不翻转。

对应的看列状态,设 \(a_i\) 表示 \(i\) 这种状态的出现次数,\(b_i\) 表示二进制数 \(i\) 的 \(0/1\) 较小值。

那么当枚举的行翻转状态为 \(x\) ,那么 \(ans=\sum_{i=0}^{2^n} a_ib_{i\text{xor} x}\) 。

变一下就有 \(ans=\sum\limits_{i\text{xor}j=x} a_ib_{j}\) ,那么我们就可以用 \(\text{xor}\) 卷积一次求出所有行翻转状态的答案,最后取 \(\min\) 就是答案。

  • P6097 【模板】子集卷积

如果没有 \(i\&j=0\) 这是好做的。

注意到 \(i|j=s,i\&j=0\) 等价于 \(i|j=s,|i|+|j|=|s|\) 。

那么我们可以把单个的值换成是一个多项式,把上面提到的加法、乘法都转换成多项式的加法、乘法,之后就是一模一样的了。

复杂度是 \(O(n\log^2 n)\) 的。

实现上可以把多项式维度转移到前面,可以结合代码理解。

还有一个形如 \(S[s]=C[s]\sum\limits_{\small t\subsetneq s}S[t]W[s-t]\) 这样的dp也可以通过子集卷积来优化。

题目:P4221 [WC2018]州区划分 。

没有什么特别重要的,就直接给题解链接了

还有一些板子,就不说了。

高级运用

复杂理论的用处来了。

  • CF449D Jzzhu and Numbers

因为这题是要求一堆数与起来为 \(0\) ,和我们上面所处理的两个数异或起来不同,这很像几个多项式乘在一起。

那么我们就可以构造多项式 \(F_i\),其中 \(F_{i}[m]=F_i[a_i]=1,m=2^n-1\) 这样在 于卷积 意义下分别表示 不选、选 \(a_i\) 。

那么答案就是 \(F(x)=[x^0]\prod_{i} F_i(x)\) ,但暴力乘起来的复杂度是 \(O(n^2\log n)\) 的。

每个多项式都只有两个非 \(0\) 项,我们来寻找一下规律:

设 \(c(i,j)\) 为and卷积的变换系数,则 \(fwt[F_k]_i=\sum\limits_{j=0}^{m}c(i,j)F_k[j]=c(i,m)+c(i,a_k)\) 。

经过我们上面的分析,\(c(i,j)=[i\&j=i]\) ,那么我们就知道:

因为 \(fwt[F(x)]_i=\prod\limits_{k=1}^nfwt[F_k]_i\) ,那么我们只要知道第 \(i\) 位有多少个 \(2\) ,那么 \(fwt[F(x)]_i\) 就等于 \(2\) 的多少次方。相当于对每个 \(i\) 求有多少个 \(a_k\&i=i\) ,就是或卷积。

求出来之后直接再逆操作转成 \(F(x)\) 即可。

  • CF1119H Triple

仿照上题,我们设 \(F_k(x)\) ,其中 \(F_k[a_k]=x,F_k[b_k]=y,F_k[c_k]=z\) ,答案为 \([x^i]\prod F_k(x)\) 。

同样 \(fwt[F_k]_i=c(i,a_k)x+c(i,b_k)y+c(i,c_k)z\) ,然后有 \(c(i,j)=(-1)^{|i\&j|}\) 。

那么 \(fwt[F(x)]_i=\prod\limits_{k=1}^nfwt[F_k]_i=\prod\limits_{k=1}^n(-1)^{|i\&a_k|}x+(-1)^{|i\&b_k|}y+(-1)^{|i\&c_k|}z\) 。

到了这里,发现我们无法适用上面的解法了,因为后面的式子比较复杂。

但是因为 \((-1)^{|i\&a_k|}x+(-1)^{|i\&b_k|}y+(-1)^{|i\&c_k|}z\) 只有 \(8\) 种取值,如果我们分别得到其个数,就可以用快速幂得到答案。

\(8\) 种还是太多了,有一种巧妙的化简方法 :

由异或的自反性,每个把三元组 \(\{a_i,b_i,c_i\}\) 异或上 \(a_i\) ,变为 \(\{0,b_i\oplus a_i,c_i\oplus a_i\}\)。

那么最后的结果异或上 \(\oplus_{i=1}^na_i\) 就能得到原来的答案。

所以就变成了 \(4\) 种。

对于 \(i\) 来说,我们设 \(c_1,c_2,c_3,c_4\) 分别表示 \(x+y+z,x+y-z,x-y+z,x-y-z\) 的个数。

那么 \(c_1=\sum\limits_{k=1}^n [(-1)^{|i\&b_k| }=1\and (-1)^{|i\&c_k| }=1]\) ,同样可以得到 \(c_2,c_3,c_4\) 的含义。

发现这和异或情况下的 \(c(i,j)\) 的系数很相似。

我们可以令 \(F_k[b_k]=1\) ,即 \(x=0,y=1,z=0\) ,那么此时 \(fwt[F_k]_i=(-1)^{|i\&b_k|}\) ,于是 \(\sum\limits_{k=1}^nfwt[F_k]_i=p1=c_1+c_2-c_3-c_4\) 。

怎么求 \(\sum\limits_{k=1}^nfwt[F_k]_i\) ,我们有 \(fwt(F+G)=fwt(F)+fwt(G)\) ,因为这东西是一个线性变换,其实就是向量乘矩阵 ,那么我们计算 \(fwt(\sum\limits_{k=1}^nF_k)\) 就可以了。

同样的,还有 令 \(F_k[c_k]=1\) ,此时 \(\sum\limits_{k=1}^nfwt[F_k]_i=p1=c_1-c_2+c_3-c_4\) 。

令 \(F_k[b_k]=F_k[c_k]=1\) ,此时 \(\sum\limits_{k=1}^nfwt[F_k]_i=p1=c_1-c_2-c_3+c_4\) 。

还有 \(c_1+c_2+c_3+c_4=n\) ,那么就可以解方程解出 \(c_1,c_2,c_3,c_4\) 的值了。

最后像上题一样逆操作转成 \(F(x)\) 即可。

和多项式高级操作的结合

没想到吧,这玩意还可以求逆、ln、exp,小编也没想到,所以这部分就咕咕咕了。

到时候再补吧

————————

This is part of the make-up plan.

Then go straight to the point.

theoretical basis

Used to solve the method of solving \ (a \ oplus B \), where (\ (\ oplus \) is a binary operation)

The name is very advanced. In fact, the basic idea is relatively simple.

快速莫比乌斯/沃尔什变换 (FMT/FWT) 

Suppose there is a sequence \ (a \), we can get another sequence \ (FWT [a] \) through some transformation. If the calculation of the complexity of the whole sequence \ (a \) is \ (O (n ^ 2) \) can be equivalent to the calculation of \ (o (n) \) in \ (FWT [a] \), the complexity of the whole process will be reduced as long as the complexity of this transformation is very low.

For example, the convolution of two functions is not easy to solve, but we can use the complexity of \ (O (n \ log n) \) to calculate its < strong > point value < / strong >, and the operation of point value is equivalent to the calculation of the original function, so the complexity of the whole FFT is \ (O (n \ log n) \).

It is more complicated to explain this transformation. It is recommended to understand the specific operation through the template problem solving area before learning the theory.

Here we will pick some of the key points and omit some proofs. For a comprehensive explanation, see here.

  • FWT is a linear transformation, that is, you can understand that \ (a \) is a \ (n \) dimensional vector, and the transformation is a \ (n \ times n \) matrix \ (C \), \ (FWT [a] _i = \ sum \ limits_{J = 0} ^ {n-1} a_j c_{I, J} \).
  • Because \ (\ oplus \) is a binary operation, we can consider each bit separately (split by bit).
    Let \ (a_0 \) be the part of the power series whose subscript first is \ (0 \), similarly \ (a_1 \).
    If \ (i_0 = 0 \), there are:
    \(fwt[A]_i=c(0,0)fwt[A_0]_ i+c(0,1)fwt[A_1]_ i\quad \big(i\in[0,n/2)\big)\)
    If \ (i_0 = 1 \), there are:
    \(fwt[A]_{i+(n/2)}=c(1,0)fwt[A_0]_ i+c(1,1)fwt[A_1]_ i\quad \big(i\in[0,n/2)\big)\)
    Therefore, for the \ (C \) matrix, only \ (C ([0,1], [0,1]) \) is useful.
  • If \ (i_0 = 0 \), there are:
    \(fwt[A]_i=c(0,0)fwt[A_0]_ i+c(0,1)fwt[A_1]_ i\quad \big(i\in[0,n/2)\big)\)
  • If \ (i_0 = 1 \), there are:
    \(fwt[A]_{i+(n/2)}=c(1,0)fwt[A_0]_ i+c(1,1)fwt[A_1]_ i\quad \big(i\in[0,n/2)\big)\)
  • \(FWT [a] \) is transformed back to \ (a \) through the inverse matrix of \ (C \), because \ (a * C = FWT [a] \ rightarrow FWT [a] * C ^ {- 1} = a \).

Template

or

That is, solve \ (c_i = \ sum \ limits_{j|k = I} a_jb_k \).

  • Matrix: \ (\ begin {bMatrix} 1 & 0 \ \ 1 & 1 \ end {bMatrix} \).
    That is \ (FWT [a] _i = FWT [a_0] _i \; \; FWT [a] _ {I + (n / 2)} = FWT [a_0]_ i+fwt[A_1]_ i\) 。
    \(c(i,j)=[i|j=i]\) 。
    Meaning: subset summation (high-dimensional prefix sum)
  • Inverse matrix: \ (\ begin {bMatrix} 1 & 0 \ \ – 1 & 1 \ end {bMatrix} \).
    That is \ (FWT [a] _i = FWT [a_0] _i \; \; FWT [a] _ {I + (n / 2)} = – FWT [a_0]_ i+fwt[A_1]_ i\) 。
    Meaning: high dimensional prefix difference.

And

That is, solve \ (c_i = \ sum \ limits {UJ \ & amp; k = I} a_jb_k \).

  • Matrix: \ (\ begin {bMatrix} 1 & 1 \ \ 0 & 1 \ end {bMatrix} \).
    That is \ (FWT [a] _i = FWT [a_0] _i + FWT [a_1] _i \; \; FWT [a] _ {I + (n / 2)} = FWT [a_1]_ i\) 。
    \(c(i,j)=[i\&j=i]\) 。
    Meaning: superset summation (high dimensional suffix sum)
  • Inverse matrix: \ (\ begin {bMatrix} 1 & – 1 \ \ 0 & 1 \ end {bMatrix} \).
    That is \ (FWT [a] _i = FWT [a_0] _i-fwt [a_1] _i \; \; FWT [a] _ {I + (n / 2)} = FWT [a_1]_ i\) 。
    Meaning: high dimensional suffix difference.

XOR

That is, solve \ (c_i = \ sum \ limits {UJ \ text {XOR} k = I} a_jb_k \).

  • Matrix: \ (\ begin {bMatrix} 1 & 1 \ \ 1 & – 1 \ end {bMatrix} \).
    That is \ (FWT [a] _i = FWT [a_0] _i + FWT [a_1] _i \; \; FWT [a] _ {I + (n / 2)} = FWT [a_1]_ i-fwt[A_1]_ i\) 。
    \(c(i,j)=(-1)^{|i\&j|}\) 。
    Meaning: I don’t know
  • Inverse matrix: \ (\ begin {bMatrix} 0.5 & 0.5 \ \ 0.5 & – 0.5 \ end {bMatrix} \).
    That is \ (FWT [a] _i = \ frac {1} {2} (FWT [a_0] _i + FWT [a_1] _i) \; \; fwt[A]_ {i+(n/2)}=\frac{1}{2}(fwt[A_1]_i-fwt[A_1]_i)\) 。

The complexity of the code is \ (O (n \ log n) \).

Examples

  • CF662C Binary Table

Because \ (n \) is very small, we can consider whether to turn every line.

For the corresponding column viewing status, set \ (a_i \) to represent the occurrence times of this status, and \ (b_i \) to represent the smaller value of \ (0 / 1 \) of binary number \ (I \).

Then, when the row flip status of the enumeration is \ (x \), then \ (ANS = \ sum {I = 0} ^ {2 ^ n} a_ib {I \ text {XOR} x} \).

Change to \ (ANS = \ sum \ limits {I \ text {XOR} J = x} a_ib {UJ} \), then we can convolute with \ (\ text {XOR} \) to find the answer of all rows in the flipped state, and finally take \ (\ min \) as the answer.

  • P6097 [template] subset convolution

If there is no \ (I \ & amp; J = 0 \), this is easy to do.

Note that \ (i|j = s, I \ & amp; J = 0 \) is equivalent to \ (i|j = s, |i| + |j| = | s124\).

Then we can change a single value into a polynomial, and convert the above-mentioned addition and multiplication into polynomial addition and multiplication, and then it will be exactly the same.

The complexity is \ (O (n \ log ^ 2 n) \).

In terms of implementation, the polynomial dimension can be transferred to the front, which can be understood in combination with the code.

Another DP in the form of \ (s [S] = C [S] \ sum \ limits {\ small t \ subsetneq s} s [t] w [S-T] \) can also be optimized by subset convolution.

Title: p4221 [wc2018] state division.

If there is nothing particularly important, you can directly link to the problem solution

There are still some boards, I won’t say.

Advanced application

The usefulness of complex theory has come.

  • CF449D Jzzhu and Numbers

Because this problem requires a pile of numbers to be \ (0 \), which is different from the XOR of the two numbers we dealt with above, which is very similar to the multiplication of several polynomials.

Then we can construct a polynomial \ (f_i \), where \ (f_ {I} [M] = f_i [a_i] = 1, M = 2 ^ n-1 \) in the sense of convolution, which means not selecting and selecting \ (a_i \) respectively.

Then the answer is \ (f (x) = [x ^ 0] \ prod_ {i} F_ I (x) \), but the complexity multiplied by violence is \ (O (n ^ 2 \ log n) \).

Each polynomial has only two non \ (0 \) terms. Let’s find the following law:

Let \ (C (I, J) \) be the transformation coefficient of and convolution, then \ (FWT [f_k] _i = \ sum \ limits {J = 0} ^ {m} C (I, J) f_ k[j]=c(i,m)+c(i,a_k)\) 。

After our above analysis, \ (C (I, J) = [I \ & amp; J = I] \), we know:

Because \ (FWT [f (x)]_ i=\prod\limits_ {k=1}^nfwt[F_k]_ I \), then we just need to know how many \ (2 \) there are in the \ (I \) bit, then \ (FWT [f (x)]_ I \) is equal to the power of \ (2 \). It is equivalent to finding the number of \ (a_k \ & amp; I = I \) for each \ (I \), which is or convolution.

After the solution is obtained, directly reverse the operation to \ (f (x) \).

  • CF1119H Triple

Following the above question, we set \ (f_k (x) \), where \ (f_k [a_k] = x, f_k [b_k] = y, f_k [c_k] = Z \), and the answer is \ ([x ^ I] \ prod f_k (x) \).

Similarly \ (FWT [f_k] _i = C (I, a_k) x + C (I, b_k) y + C (I, c_k) Z \), followed by \ (C (I, J) = (- 1) ^ | I \ & amp; j|} \).

Then \ (FWT [f (x)]_ i=\prod\limits_ {k=1}^nfwt[F_k]_ i=\prod\limits_ {k=1}^n(-1)^{|i\&a_k|}x+(-1)^{|i\&b_k|}y+(-1)^{|i\&c_k|}z\) 。

Here, we find that we can’t apply the above solution, because the latter formula is more complex.

However, because \ (- 1) ^ | I \ & amp; a_k | x + (- 1) ^ | I \ & amp; b_k | y + (- 1) ^ {| I \ & amp; c_k | Z \) has only \ (8 \) values, if we get their numbers respectively, we can use the fast power to get the answer.

\(8 \) there are still too many. There is a clever simplification method:

By the reflexivity of XOR, each triplet \ (\ {a_i, b_i, c_i \} \) XOR up \ (a_i \) is changed into \ (\ {0, b_i \ oplus a_i, c_i \ oplus a_i \} \).

Then the final result of XOR (\ oplus {I = 1} ^ Na _i \) will get the original answer.

So it becomes \ (4 \).

For \ (I \), let \ (c_1, c_2, c_3, c_4 \) represent the number of \ (x + y + Z, x + Y-Z, X-Y + Z, X-Y-Z \).

Then \ (c_1 = \ sum \ limits {k = 1} ^ n [(- 1) ^ {I \ & amp; b_k} = 1 \ and (- 1) ^ {I \ & amp; c_k} = 1] \), you can also get the meaning of \ (c_2, c_3, c_4 \).

It is found that this is very similar to the coefficient of \ (C (I, J) \) in the case of XOR.

We can make \ (f_k [b_k] = 1 \), i.e. \ (x = 0, y = 1, z = 0 \), then at this time \ (FWT [f_k] _i = (- 1) ^ | I \ & amp; b_k|} \), so \ (\ sum \ limits {k = 1} ^ nfwt [f_k] _i = P1 = c_1 + c_2-c_3-c_4 \).

How to find \ (\ sum \ limits {k = 1} ^ nfwt [f_k] _i \), we have \ (FWT (F + G) = FWT (f) + FWT (g) \), because this thing is a linear transformation, which is actually a vector multiplication matrix, so we can calculate \ (FWT (\ sum \ limits {k = 1} ^ nf_k) \).

Similarly, let \ (f_k [c_k] = 1 \) and at this time \ (\ sum \ limits {k = 1} ^ nfwt [f_k] _i = P1 = c_1-c_2 + c_3-c_4 \).

Make \ (f_k [b_k] = f_k [c_k] = 1 \), and at this time \ (\ sum \ limits {k = 1} ^ nfwt [f_k] _i = P1 = c_1-c_2-c_3 + c_4 \).

And \ (c_1 + c_2 + c_3 + c_4 = n \), then you can solve the equation to solve the value of \ (c_1, c_2, c_3, c_4 \).

Finally, as in the previous question, reverse the operation to \ (f (x) \).

Combination of polynomial and advanced operation

Unexpectedly, this thing can also calculate the inverse, LN and exp. Xiaobian didn’t expect it, so this part is cooing.

Make it up then