Polynomial $A(x) = \sum_{j=0}^{n-1} a_j x^j$

let coeffs $A = (a_0,...,a_{n-1})$.

that $k=0,...,n-1$
$$
\begin{align}
\text{DFT}(A) &= (\sum_{j=0}^{n-1} a_j e^{-\frac{2\pi i}{n} jk},...)_k \\
    &= (A(\omega_n^k),...)_k,\ \ \  \omega_n^k = \exp(-\frac{2\pi i}{n} k)
\end{align}
$$

then consider convolution, or multiplication of $A(x)$ and $B(x)$. we wanna know coeffs of  $(A*B)(x) = A(x)B(x)$.

for simplicity write $F=DFT$, notice that, $F(A) = (A(\omega_n^k))_k$, that

$$
\begin{align}
    F(A*B)  &= ((A*B)(\omega_n^k))_k = (A(\omega_n^k)B(\omega_n^k))_k = F(A)\cdot  F(B) \\
    A*B &= F^{-1}[F(A)\cdot  F(B)]
\end{align}
$$

so next we need is to compute $F, F^{-1}$ in $O(n\log n)$

Before continue, note the lemmas

$$
\begin{align}
    \omega_{dn}^{dk} = \omega_n^k, n,k,d \geq 0 \\
    \omega_n^{n/2} = \omega_2^1 = -1,  n>0 \\
    (\omega_n^{k+n/2})^2=(\omega_n^k)^2=\omega_{n/2}^k, n>0, \text{even} \\
    \omega_n^{k+n/2} = -\omega_n^k, n\geq 0
\end{align}
$$

then by separate odd,even, i.e. $A(x) = A_0(x^2) + xA_1(x^2)$. combine above lemmas, get

$$
\begin{align}
    A(\omega_n^k) = A_0(\omega_{n/2}^k) + \omega_n^k A_1(\omega_{n/2}^k), 0\leq k < n/2 \\
    A(\omega_n^{k+n/2}) = A_0(\omega_{n/2}^k) - \omega_n^k A_1(\omega_{n/2}^k), k+n/2 \geq n/2
\end{align}
$$

Thus, by divide and conquer solved. what about $F^{-1}$. notice that matrix form

$$
\begin{align}
    y=F(A) = W a \\
    w_{k,j} = \omega_n^{kj}, k,j=0,...n-1\\
    a = F^{-1}(y) = W^{-1}y
\end{align}
$$

by the special form of $W$
$$
\begin{align}
    W^{-1} = \frac{1}{n} \bar{W}\\
    v_{kj} = \frac{1}{n} \bar{w_n} ^{kj}
\end{align}
$$

So, just conjugate and divided by $n$. then same method sovlable.

### NTT

let $\alpha$ replace $\omega_n$ in integer field.

DFT require
$$
\begin{align}
    \sum_{j=0}^{n-1} \alpha^{kj} = 0, k=1,...,n-1
\end{align}
$$
and $\alpha^n=1, \alpha^k \neq 1, k=1,...,n-1$ is sufficient

if $n$ is power of $2$, $\alpha^{n/2} = -1$ is sufficient

if we get the $\alpha$ on $Z_p$, then $p=c2^k+1$, that $\alpha^c$ can be the $\alpha'$ to express conv length $\leq 2^{k-1}$

For in place NTT, leaves' addr. are bit-reversed. (NEED rigorous proof)

and if for $F^{-1}$, one way is calc $\alpha^{-1}$, for each iter. Here is another way. Notice the matrix form. suppose $a$ divided by $n$, then we reverse $[a_1,...,a_{n-1}]$. by the fact $\alpha^{k(n-j)} = \alpha^{-kj}$, thus result is exactly $F^{-1}$. 

#### inverse

we wanna know $BA \equiv 1 (\mod x^n)$. by the step that double $B$'s size, with init $B_0=1/A_0$. wlog write $B_1$ repre. $B_n$, $B_2$ repre. $B_{2n}$. that
$$
\begin{align}
    & (B_1 A - 1)^2 \equiv 0 (\mod x^2) \\
    \Rightarrow  & B_2 = 2B_1 - B_1^2 A (\mod x^2)
\end{align}
$$
note, in impl. $B_1^2A$ has $B_1(\mod x)$ part in there since $B_1A \equiv 1(\mod x)$. aka, $(\mod x)$ part remain $B_1$, actually, we only need modify the higher order part, $-B_1^2 A ([x\leq..<x^2])$ 

#### sqrt

also, the double size technique
$$
\begin{align}
    & (B_1^2 - A)^2 \equiv 0 (\mod x^2) \\
    \Rightarrow  & B_2 = \frac{1}{2} [B_1 + A B_1^{-1}](\mod x^2)
\end{align}
$$
again, notice the old part $B_1$ shall remain, we can only modify new part in impl. and careful $B_0^2=A_0$ when $\neq 1$

#### log

$\log P = \int \frac{P'}{P}$

#### exponent

double step, $B_2 = B_1(1 + A - \log B_1)$

### FWHT(FHT)

Hadamard transform, def, with $H_0 = 1$
$$
\begin{align}
    H_m = \frac{1}{\sqrt{2}} \begin{bmatrix} H_{m-1} & H_{m-1} \\ H_{m-1} & -H_{m-1} \end{bmatrix} \\
    (H_m)_{i,j} = \frac{1}{2^{m/2}} (-1)^{\langle i, j \rangle_b}
\end{align}
$$
where $i,j= 0,1,..,2^m-1$ and $\langle .,.\rangle_b$ is bitwise dot product, aka
```
__builtin_popcount(i&j)
```

when do fwht, don't need bit reversal and generator. besides, there is good property $H_m^2= I$.
One can easy show $H_1^2 = I$ by direct compute or quantum tech. $H_1 = |+\rangle \langle 0| + |-\rangle \langle 1| $. then by induction. $H_m = H_1 \otimes H_{m-1}$. that $H_m^2 = H_1^2 \otimes H_{m-1}^2 = I$. which means we can do $H^{-1}$ by direct do $H$ !

note in impl. we often omit $2^{n/2}$, that use $H' = 2^{n/2}H$. so when do inverse, we need divide by $2^n$.

still, we can do multiply by $A*B = H^{-1} [H(A) \cdot H(B)]$. note $\cdot$ is element-wise mult.

also, suprisingly, for solving equation $A*B = C$, if we put $H$ on each side, that

$H(A) \cdot H(B) = H(C)$, since $\cdot$ is element-wised, thus we can get $A = H^{-1} [H(C) / H(B)]$, element-wise.

Note. for $\sum_i B_i = 0$, aka, not linear indep. the solution may has many, notice that $R = (1,1,...,1)$, that $R*B = 0$. e.g. agc034f.

so we can minus arbitral still solution, but according specific condition, we can get the right one.

### useful links

https://cp-algorithms.com/algebra/fft.html

https://cp-algorithms.com/algebra/polynomial.html#toc-tgt-4

https://en.wikipedia.org/wiki/Discrete_Fourier_transform#Polynomial_multiplication

https://en.wikipedia.org/wiki/Discrete_Fourier_transform_(general)

https://codeforces.com/blog/entry/43499

https://codeforces.com/blog/entry/48798

https://crypto.stanford.edu/pbc/notes/numbertheory/gen.html

https://csacademy.com/blog/fast-fourier-transform-and-variations-of-it


```python

```

ba2c899d1c4766738dc6c34cee0ca0e8186e3f78
ipynb
Jupyter Notebook
notes/FFT.ipynb
sogapalag/problems
0ea7d65448e1177f8b3f81124a82d187980d659c
MIT
2020-04-04T14:56:12.000Z
2020-04-04T14:56:12.000Z
notes/FFT.ipynb
sogapalag/problems
0ea7d65448e1177f8b3f81124a82d187980d659c
MIT
notes/FFT.ipynb
sogapalag/problems
0ea7d65448e1177f8b3f81124a82d187980d659c
MIT
Qwen/Qwen-72B
1. YES
2. YES