# 0x00 前言

(好罢主要是给 myh 看的手动 @ybmyh)

# 0x01 点值表示法

$$F(x)=\sum_{i=0} ^ {n}a_{i}\times x ^ {i}$$

# 0x02 复数和单位根

$(a+bi)+(c+di)=(a+c)+(b+d)i$

$(a+bi)-(c+di)=(a-c)+(b-d)i$

$(a+bi)\times(c+di)=ac+adi+bci-bd=(ac-bd)+(ad+bc)i$

$k$ 表示第 $k$ 个 $n$ 次单位根，从 0 开始标号，$\omega ^ {0} _ {n},\omega ^ {1} _ {n},\cdots,\omega ^ {n-1} _ {n},$。其中 $\omega^{0}_{n}=1$。

\begin{align}\label{2} & \omega^{k} _ {n}=e^{\frac{2k\pi}{n}i}=\cos\frac{2k\pi}{n}i+i\sin\frac{2k\pi}{n} \tag{2.1} \\ & \omega^{0} _ {n}=1 \tag{2.2} \\ & \omega^{k} _ {n}=\omega^{k\operatorname{mod} n} \tag{2.3} \\ & \omega^{k} _ {n}\times\omega^{j} _ {n}=\omega^{k+j} _ {n} \tag{2.4} \\ & (\omega^{1} _ {n})^{k}=\omega^{k} _ {n} \tag{2.5} \\ & \omega^{pk} _ {pn}=\omega^{k} _ {n} \tag{2.6} \\ & \omega^{k+\frac{n}{2}} _ {n}=-\omega ^ {k} _ {n} \tag{2.7} \\ \end{align}

# 0x03 继续研究多项式

$$F(x)=\sum_{i=0}^{n-1}a_{i}\times x^{i}$$

$$F(x)=\sum_{i=0}^{n-1}a_{i}\times x^{i}=\sum_{i=0}^{\frac{n}{2}-1}a_{2i}\times x^{2i}+\sum_{i=0}^{\frac{n}{2}-1}a_{2i+1}\times x^{2i+1}$$

$$L(x)=\sum_{i=0}^{\frac{n}{2}-1}a_{2i}\times x^{i}$$

$$R(x)=\sum_{i=0}^{\frac{n}{2}-1}a_{2i+1}\times x^{i}$$

$$\begin{array}{l} F(x)&=\sum_{i=0}^{n-1}a_{i}\times x^{i} \\ &=\sum_{i=0}^{\frac{n}{2}-1}a_{2i}\times x^{2i}+\sum_{i=0}^{\frac{n}{2}-1}a_{2i+1}\times x^{2i+1} \\ &=\sum_{i=0}^{\frac{n}{2}-1}a_{2i}\times (x^{2})^{i}+\sum_{i=0}^{\frac{n}{2}-1}a_{2i+1}\times (x^{2})^{i}\times x \\ &=\sum_{i=0}^{\frac{n}{2}-1}a_{2i}\times x^{2i}+\sum_{i=0}^{\frac{n}{2}-1}a_{2i+1}\times x^{2i+1}\\ &=L(x^{2})+xR(x^{2}) \end{array}$$

$$F(x)=L(x^{2})+xR(x^{2})$$

$$F(\omega_{n}^{k})=L(\omega_{n}^{2k})+\omega_{n}^{k}R(\omega_{n}^{2k})$$

$$F(\omega_{n}^k)=L(\omega_{2\times \frac{1}{2}n}^{2k})+\omega_{n}^{k}R(\omega_{2\times \frac{1}{2}n}^{2k})$$

$$F(\omega_{n}^{k})=L(\omega_{\frac{1}{2}n}^{k})+\omega_{n}^{k}R(\omega_{\frac{1}{2}n}^{k}) \tag{3.1}$$

$$F(x)=L(x^{2})+xR(x^{2})$$

$$F(\omega_{n}^{k+\frac{n}{2}})=L(\omega_{\frac{n}{2}}^{k})-R(\omega_{\frac{n}{2}}^{k}) \tag{3.2}$$

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <complex>

using namespace std;

const double PI = acos(-1);
const int MAXN = 1e6 + 3e5 + 5;
int n;

struct Complex {
double real;
double imag;
Complex(double t_real = 0, double t_imag = 0) { real = t_real, imag = t_imag; }
Complex operator + (Complex const& rhs) const {
return Complex(real + rhs.real, imag + rhs.imag);
}
Complex operator - (Complex const& rhs) const {
return Complex(real - rhs.real, imag - rhs.imag);
}
Complex operator * (Complex const& rhs) const {
return Complex(real * rhs.real - imag * rhs.imag, real * rhs.imag + imag * rhs.real);
}
void to_real(const double t_real) {
real = t_real;
}
void to_imag(const double t_imag) {
imag = t_imag;
}
double to_real() {
return real;
}
double to_imag() {
return imag;
}
} F[MAXN << 2], t[MAXN << 2];

void dft(Complex *f, int __n) {
if (__n == 1) return ;
Complex *L = f;
Complex *R = f + (__n >> 1);
for (int k = 0; k < __n; ++k) t[k] = f[k];
for (int k = 0; k < (__n >> 1); ++k) L[k] = t[k << 1], R[k] = t[k << 1 | 1];
dft(L, (__n >> 1));
dft(R, (__n >> 1));
Complex omega;
Complex now;
omega.to_real(cos(2 * PI / __n));
omega.to_imag(sin(2 * PI / __n));
now.to_real(1);
now.to_imag(0);
for (int k = 0; k < (__n >> 1); ++k) {
t[k] = L[k] + now * R[k];
t[k + (__n >> 1)] = L[k] - now * R[k];
now = now * omega;
}
for (int k = 0; k < __n; ++k) f[k] = t[k];
}

signed main() {
scanf("%d", &n);
int temp = n;
double x;
for (n = 1; n < temp; n <<= 1) ;
for (int i = 0; i < temp; ++i) scanf("%lf", &x), F[i].to_real(x), F[i].to_imag(0);
dft(F, n);
for (int i = 0; i < n; ++i) printf("(%.2lf %.2lf)\n", F[i].to_real(), F[i].to_imag());
return 0;
}


subarashi

IDFT 的证明比较繁琐，涉及到分类讨论。由于我最近被数学作业的多答案讨论和智障珠的 60 种情况毒瘤了，故懒得给出证明。反正我相信看我 blog 的人人均会单位根反演

$$G=\mathcal{F}(F(x))$$

$$n\times f_{k}=\sum_{i=0}^{n-1}\omega_n^{-ki}g_{i}$$

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <complex>

using namespace std;

const double PI = acos(-1);
const int MAXN = 1e6 + 3e5 + 5;
int n, m;
struct Complex {
double real;
double imag;
Complex(double t_real = 0, double t_imag = 0) { real = t_real, imag = t_imag; }
Complex operator + (Complex const& rhs) const {
return Complex(real + rhs.real, imag + rhs.imag);
}
Complex operator - (Complex const& rhs) const {
return Complex(real - rhs.real, imag - rhs.imag);
}
Complex operator * (Complex const& rhs) const {
return Complex(real * rhs.real - imag * rhs.imag, real * rhs.imag + imag * rhs.real);
}
void to_real(const double t_real) {
real = t_real;
}
void to_imag(const double t_imag) {
imag = t_imag;
}
double to_real() {
return real;
}
double to_imag() {
return imag;
}
} A[MAXN << 2], B[MAXN << 2], t[MAXN << 2];

void dft(Complex *f, int __n, int flag) {
if (__n == 1) return ;
Complex *L = f;
Complex *R = f + (__n >> 1);
for (int k = 0; k < __n; ++k) t[k] = f[k];
for (int k = 0; k < (__n >> 1); ++k) L[k] = t[k << 1], R[k] = t[k << 1 | 1];
dft(L, (__n >> 1), flag);
dft(R, (__n >> 1), flag);
Complex omega;
Complex now;
omega.to_real(cos(2 * PI / __n));
omega.to_imag(sin(2 * PI / __n) * flag);
now.to_real(1);
now.to_imag(0);
for (int k = 0; k < (__n >> 1); ++k) {
t[k] = L[k] + now * R[k];
t[k + (__n >> 1)] = L[k] - now * R[k];
now = now * omega;
}
for (int k = 0; k < __n; ++k) f[k] = t[k];
}

signed main() {
scanf("%d %d", &n, &m);
double x;
for (int i = 0; i <= n; ++i) scanf("%lf", &x), A[i].to_real(x), A[i].to_imag(0);
for (int i = 0; i <= m; ++i) scanf("%lf", &x), B[i].to_real(x), B[i].to_imag(0);
for (m += n, n = 1; n <= m; n <<= 1) ;
dft(A, n, 1);
dft(B, n, 1);
for (int i = 0; i < n; ++i) A[i] = A[i] * B[i];
dft(A, n, -1);
for (int i = 0; i <= m; ++i) printf("%d ", (int)(A[i].real / n + 0.49));
return 0;
}


$$\texttt{0 1 2 3 4 5 6 7}$$

$$\texttt{(000) (001) (010) (011) (100) (101) (110) (111)}$$

$$\texttt{(000) (100) (010) (110) (001) (101) (011) (111)}$$

$$\texttt{0 4 2 6 1 5 3 7}$$

int lim = 0;
while ((1 << lim) < n) ++lim;
for (int i = 0; i < n; ++i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (lim - 1));


#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <complex>

using namespace std;

const double PI = acos(-1);
const int MAXN = 1e6 + 3e5 + 5;
int n, m;

struct Complex {
double real;
double imag;
Complex(double t_real = 0, double t_imag = 0) { real = t_real, imag = t_imag; }
Complex operator + (Complex const& rhs) const {
return Complex(real + rhs.real, imag + rhs.imag);
}
Complex operator - (Complex const& rhs) const {
return Complex(real - rhs.real, imag - rhs.imag);
}
Complex operator * (Complex const& rhs) const {
return Complex(real * rhs.real - imag * rhs.imag, real * rhs.imag + imag * rhs.real);
}
void to_real(const double t_real) {
real = t_real;
}
void to_imag(const double t_imag) {
imag = t_imag;
}
double to_real() {
return real;
}
double to_imag() {
return imag;
}
} A[MAXN << 2], B[MAXN << 2], t[MAXN << 2];
int rev[MAXN << 2];

void get_rev() {
int lim = 0;
while ((1 << lim) < n) ++lim;
for (int i = 0; i < n; ++i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (lim - 1));
}

void fft(Complex *f, int __n, int flag) {
for (int i = 0; i < n; ++i) if (i < rev[i]) swap(f[i], f[rev[i]]);
for (int mid = 1; mid < lim; mid <<= 1) {
Complex omega;
omega.to_real(cos(PI / mid));
omega.to_imag(sin(PI / mid) * flag);
for (int i = 0; i < n; i += (mid << 1)) {
Complex now;
now.to_real(1);
now.to_imag(0);
for (int j = 0; j < mid; ++j) {
Complex first = f[i + j];
Complex second = now * f[i + j + mid];
f[i + j] = first + second;
f[i + j + mid] = first - second;
now = now * omega;
}
}
}
}

signed main() {
scanf("%d %d", &n, &m);
double x;
for (int i = 0; i <= n; ++i) scanf("%lf", &x), A[i].to_real(x), A[i].to_imag(0);
for (int i = 0; i <= m; ++i) scanf("%lf", &x), B[i].to_real(x), B[i].to_imag(0);
for (m += n, n = 1; n <= m; n <<= 1) ;
get_rev();
fft(A, n, 1);
fft(B, n, 1);
for (int i = 0; i < n; ++i) A[i] = A[i] * B[i];
fft(A, n, -1);
for (int i = 0; i <= m; ++i) printf("%d ", (int)(A[i].real / n + 0.49));
return 0;
}