fwt小记(FWT notes)-其他

fwt小记(FWT notes)

理论基础

• 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$$ 。

或

• 矩阵： $$\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$$ 。
含义：高维前缀差。

与

• 矩阵： $$\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$$ 。
含义：高维后缀差。

异或

• 矩阵： $$\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)$$ 。

例题

• CF662C Binary Table

• P6097 【模板】子集卷积

高级运用

• CF449D Jzzhu and Numbers

• CF1119H Triple

$$8$$ 种还是太多了，有一种巧妙的化简方法 ：

和多项式高级操作的结合

————————

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.

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 \).

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.

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