$$$$

二进制卷积

快速傅里叶变换可以高效地计算两个多项式的乘积，进而加速了卷积运算。

INFO

序列 $A$ 和序列 $B$ 的卷积记作 $C=$$A\ast$$B$，其中

$$C_k=\sum _{i+j=k}{A}_i{B}_j$$

构造多项式

$$\begin{array}{rl}A(x)& =A_0+A_{1}x+A_2{x}^2+\cdots \\ B(x)& =B_0+B_{1}x+B_2{x}^2+\cdots \end{array}$$

我们知道 $A(x)\cdot B(x)$ 中 $x^k$ 前的系数就是 $C_k$，而 $A(x)\cdot B(x)$ 的系数序列可由 FFT 得到。因此 FFT 也被认为是快速卷积算法。

现在考虑一类奇怪的卷积：

$$\sum _{i\mathrm{or}j=k}{A}_i{B}_j\sum _{i\mathrm{and}j=k}{A}_i{B}_j\sum _{i\mathrm{xor}j=k}{A}_i{B}_j$$

其中 $\mathrm{or},$$\mathrm{and},$$\mathrm{xor}$ 是二进制按位或、与、异或。下图附上了一位二进制运算的真值表。

面对这类奇葩的卷积时，FFT 就束手无策了。

$A$	$B$	$A\mathrm{or}B$	$A\mathrm{and}B$	$A\mathrm{xor}B$
0	0	0	0	0
0	1	1	0	1
1	0	1	0	1
1	1	1	1	0

还有高手？

快速沃尔什变换（Fast Walsh-Hadamard Transform，FWT）是加速 二进制卷积 运算的算法，其大方向与 FFT 非常相似。

回忆一下 FFT 如何加速多项式乘法：

EXAMPLE

1. 对 $A(x)$ 和 $B(x)$ 使用 DFT，得到两个点集：$$\begin{gathered} \{(x_i,A(x_i))\mid 0\le i<N\} \\ \{(x_i,B(x_i))\mid 0\le i<N\} \end{gathered}$$
2. 计算出 $C(x)=$$A(x)\cdot B(x)$ 的点值表示法：$$\{(x_i,A(x_i)\cdot B(x_i))\mid 0\le i<N\}$$
3. 使用 IDFT 将其转化为系数表示法。

我们在 DFT 和 IDFT 中使用 FFT 的思想来加速这个过程。

FWT 也是同样的套路：

EXAMPLE

1. 对序列 $A,$$B$ 使用 FWT，得到两个中间态（中间态也是序列）：$$\mathrm{FWT}(A),\mathrm{FWT}(B)$$
2. 使用点对点乘法，计算出 $C$ 的中间态：$$\mathrm{FWT}(C)=\{\mathrm{FWT}(A{)}_i\times \mathrm{FWT}(B{)}_i|i=0,1,2,\cdots \}$$
3. 使用 UFWT（也称 IFWT）将其还原为序列 $C$。

只不过 FWT 的中间态略显抽象，并且 $\mathrm{or},$$\mathrm{and},$$\mathrm{xor}$ 卷积所对应的中间态还各不相同。

OR 卷积

在 $\mathrm{or}$ 卷积中，序列 $X$ 对应的中间态为与之等长的序列 $\mathrm{FWT}(X)$，其中

$$\mathrm{FWT}(X{)}_k=\sum _{i\mathrm{or}k=k}{X}_i$$

🤔沃尔什究竟是怎么想出来的？

设有两个序列 $A,$$B$，待求的序列是 $C$，其中 $C_k=$$\sum _{i\mathrm{or}j=k}{A}_i{B}_j$。

可以证明，对 $A$ 和 $B$ 的中间态进行点对点乘法可以得出 $C$ 的中间态。

证

容易发现

$$a\mathrm{or}c=c,b\mathrm{or}c=c\Rightarrow (a\mathrm{or}b)\mathrm{or}c=c$$

可以从集合意义理解：若 $a\in c$ 且 $b\in c$，则 $a$ 和 $c$ 的并集也是 $c$ 的子集。

接下来的证明步骤会用到该结论。

$$\begin{array}{rl}& \mathrm{FWT}(A{)}_k\times \mathrm{FWT}(B{)}_k\\ =& \left(\sum _{i\mathrm{or}k=k}{A}_i\right)\left(\sum _{j\mathrm{or}k=k}{B}_j\right)\\ =& \sum _{i\mathrm{or}k=k,j\mathrm{or}k=k}{A}_i{B}_j\\ =& \sum _{(i\mathrm{or}j)\mathrm{or}k=k}{A}_i{B}_j\\ =& \stackrel{x=i\mathrm{or}j}{====}=\sum _{x\mathrm{or}k=k}\sum _{i\mathrm{or}j=x}{A}_i{B}_j\\ =& \sum _{x\mathrm{or}k=k}{C}_x\\ =& \mathrm{FWT}(C{)}_k\end{array}$$

证毕。

现在推导一下中间态的求法。

类似于 FFT，此处也规定所有序列的长度 $n$ 都是 $2$ 的幂次。

我们将序列 $A=$$\{A_0,A_1,\cdots ,A_{n-1}\}$ 均分为两段

$$A_{\mathrm{prev}}=\{A_0,A_1,\cdots ,A_{\frac{n}{2}-1}\}{A}_{\mathrm{back}}=\{A_{\frac{n}{2}},A_{\frac{n}{2}+1},\cdots ,A_{n-1}\}$$

然后仔细盯真 $A$ 的中间态：

$$\mathrm{FWT}(A{)}_k=\sum _{i\mathrm{or}k=k}{A}_i$$

• 当 $0\le k\le \frac{n}{2}-$$1$ 时，由 $\mathrm{or}$ 运算的性质可知，$i\mathrm{or}k=$$k$ 中 $i$ 的大小不可能超过 $k$。因此 $i$ 也落在 $0\cdots \frac{n}{2}-$$1$ 的范围内，也就是说 $A_i$ 只能来自 $A_{\mathrm{prev}}$，即 $\sum _{i\mathrm{or}k=k}{A}_i=$$\sum _{i\mathrm{or}k=k}(A_{\mathrm{prev}}{)}_i$，即$$\mathrm{FWT}(A{)}_k=\mathrm{FWT}{\left(A_{\mathrm{prev}}\right)}_k$$
• 当 $\frac{n}{2}\le k\le n-$$1$ 时，$A_i$ 既可以来自 $A_{\mathrm{prev}}$，又可以来自 $A_{\mathrm{back}}$。由于 $\mathrm{FWT}(A{)}_k$ 是一个求和式，我们可以顺理成章地把它拆成两个部分的和$$\mathrm{FWT}(A{)}_k=\mathrm{FWT}{\left(A_{\mathrm{prev}}\right)}_{k-\frac{n}{2}}+\mathrm{FWT}{\left(A_{\mathrm{back}}\right)}_{k-\frac{n}{2}}$$注：此处对 $k$ 减去 $\frac{n}{2}$ 是为了调整下标，使其适应相应的分段序列。或者说，$A_{\mathrm{prev}}$ 和 $A_{\mathrm{back}}$ 的长度都只有 $\frac{n}{2}$，作此调整可以防止数组访问越界。

即

$$\mathrm{FWT}(A{)}_k=\{\begin{array}{ll}\mathrm{FWT}{\left(A_{\mathrm{prev}}\right)}_k,& 0\le k\le \frac{n}{2}-1\\ \\ \mathrm{FWT}{\left(A_{\mathrm{prev}}\right)}_{k-\frac{n}{2}}+\mathrm{FWT}{\left(A_{\mathrm{back}}\right)}_{k-\frac{n}{2}},& \frac{n}{2}\le k\le n-1\end{array}$$

更进一步地，以序列为基本单位看问题：

$$\begin{array}{}\text{(1)}& \mathrm{FWT}(A)=\{\begin{array}{ll}A,& n=1\\ \\ \mathrm{merge}(\mathrm{FWT}\left(A_{\mathrm{prev}}\right),\mathrm{FWT}\left(A_{\mathrm{back}}\right)\oplus \mathrm{FWT}\left(A_{\mathrm{prev}}\right)),& n>1\end{array}\end{array}$$

其中 $\mathrm{merge}$ 是拼接两个序列的操作，$\oplus$ 表示两个序列的点对点加法。

---

上面我们已经剖析了 FWT 的算法，现在还需要讨论其反演 UFWT。

其实只要把点对点加法 $\oplus$ 改为点对点减法 $\ominus$ 就可以得到 UFWT 的递推式。

$$\begin{array}{}\text{(2)}& \mathrm{UFWT}(A)=\{\begin{array}{ll}A,& n=1\\ \\ \mathrm{merge}(\mathrm{UFWT}\left(A_{\mathrm{prev}}\right),\mathrm{UFWT}\left(A_{\mathrm{back}}\right)\ominus \mathrm{UFWT}\left(A_{\mathrm{prev}}\right)),& n>1\end{array}\end{array}$$

容易证明 $(2)$ 式是 $(1)$ 式的逆变换。

证

此论断等价于 $\mathrm{UFWT}(\mathrm{FWT}(A))=$$A$，这里采用数学归纳法证明。

设序列 $A$ 的长度为 $n$。当 $n=$$1$ 时命题显然成立。

由于 $n$ 始终是 $2$ 的幂次，即只需证明当 $n>1$ 时

$$\text{命题对}\frac{n}{2}\text{成立}\Rightarrow \text{命题对}n\text{成立}$$

现假设命题对 $\frac{n}{2}$ 成立。由于 $A_{\mathrm{prev}}$ 和 $A_{\mathrm{back}}$ 都是长为 $\frac{n}{2}$ 的序列，因此有

$$\mathrm{UFWT}(\mathrm{FWT}(A_{\mathrm{prev}}))=A_{\mathrm{prev}},\mathrm{UFWT}(\mathrm{FWT}(A_{\mathrm{back}}))=A_{\mathrm{back}}$$

由式 $(1)$ $(2)$ 得（将 $\mathrm{merge}$ 拆开）：

$$\begin{array}{rl}& \{\begin{array}{l}\mathrm{FWT}(A{)}_{\mathrm{prev}}=\mathrm{FWT}(A_{\mathrm{prev}})\\ \mathrm{FWT}(A{)}_{\mathrm{back}}=\mathrm{FWT}(A_{\mathrm{back}})\oplus \mathrm{FWT}(A_{\mathrm{prev}})\end{array}\\ \\ & \{\begin{array}{l}\mathrm{UFWT}(A{)}_{\mathrm{prev}}=\mathrm{UFWT}(A_{\mathrm{prev}})\\ \mathrm{UFWT}(A{)}_{\mathrm{back}}=\mathrm{UFWT}(A_{\mathrm{back}})\ominus \mathrm{UFWT}(A_{\mathrm{prev}})\end{array}\end{array}$$

因此

$$\begin{array}{rl}\mathrm{UFWT}(\mathrm{FWT}(A){)}_{\mathrm{prev}}& =\mathrm{UFWT}(\mathrm{FWT}(A{)}_{\mathrm{prev}})=\mathrm{UFWT}(\mathrm{FWT}(A_{\mathrm{prev}}))=A_{\mathrm{prev}}\\ \\ \mathrm{UFWT}(\mathrm{FWT}(A){)}_{\mathrm{back}}& =\mathrm{UFWT}(\mathrm{FWT}(A{)}_{\mathrm{back}})\ominus \mathrm{UFWT}(\mathrm{FWT}(A{)}_{\mathrm{prev}})\\ & =\mathrm{UFWT}(\mathrm{FWT}(A_{\mathrm{back}})\oplus \mathrm{FWT}(A_{\mathrm{prev}}))\ominus \mathrm{UFWT}(\mathrm{FWT}(A_{\mathrm{prev}}))\\ & =\mathrm{UFWT}(\mathrm{FWT}(A_{\mathrm{back}}))\oplus \mathrm{UFWT}(\mathrm{FWT}(A_{\mathrm{prev}}))\ominus \mathrm{UFWT}(\mathrm{FWT}(A_{\mathrm{prev}}))\\ & =A_{\mathrm{back}}\oplus A_{\mathrm{prev}}\ominus A_{\mathrm{prev}}\\ & =A_{\mathrm{back}}\end{array}$$

因此

$$\mathrm{UFWT}(\mathrm{FWT}(A))=\mathrm{merge}(A_{\mathrm{prev}},A_{\mathrm{back}})=A$$

即命题对 $n$ 成立。证毕。

模板

void FWT_OR(vector<int>& a, int l, int r, bool inv) {
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    FWT_OR(a, l, mid, inv);
    FWT_OR(a, mid + 1, r, inv);
    for (int i = 0; i <= mid - l; i ++) {
        if (!inv)
            a[mid + 1 + i] += a[l + i];
        else
            a[mid + 1 + i] -= a[l + i];
    }
}

void FWT_OR(vector<int>& a, bool inv) {
    int n = a.size();
    for (int d = 1; d < n; d <<= 1) {
        for (int m = d << 1, i = 0; i < n; i += m) {
            for (int j = 0; j < d; j ++) {
                if (!inv)
                    a[i + j + d] += a[i + j];
                else
                    a[i + j + d] -= a[i + j];
            }
        }
    }
}

AND 卷积

$\mathrm{and}$ 卷积和 $\mathrm{or}$ 卷积在本质上是类似的。

$$\mathrm{FWT}(X{)}_k=\sum _{i\mathrm{and}k=k}{X}_i$$

类似可证 $\mathrm{FWT}(A{)}_k\times \mathrm{FWT}(B{)}_k=$$\mathrm{FWT}(C{)}_k$。

由于 $\mathrm{and}$ 运算的性质，递推式的点对点加减法操作都集中在前面。

$$\begin{array}{rl}\mathrm{FWT}(A)& =\{\begin{array}{ll}A,& n=1\\ \\ \mathrm{merge}(\mathrm{FWT}\left(A_{\mathrm{prev}}\right)\oplus \mathrm{FWT}\left(A_{\mathrm{back}}\right),\mathrm{FWT}\left(A_{\mathrm{back}}\right)),& n>1\end{array}\\ \\ \mathrm{UFWT}(A)& =\{\begin{array}{ll}A,& n=1\\ \\ \mathrm{merge}(\mathrm{UFWT}\left(A_{\mathrm{prev}}\right)\ominus \mathrm{UFWT}\left(A_{\mathrm{back}}\right),\mathrm{UFWT}\left(A_{\mathrm{back}}\right)),& n>1\end{array}\end{array}$$

模板

void FWT_AND(vector<int>& a, int l, int r, bool inv) {
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    FWT_AND(a, l, mid, inv);
    FWT_AND(a, mid + 1, r, inv);
    for (int i = 0; i <= mid - l; i ++) {
        if (!inv)
            a[l + i] += a[mid + 1 + i];
        else
            a[l + i] -= a[mid + 1 + i];
    }
}

void FWT_AND(vector<int>& a, bool inv) {
    int n = a.size();
    for (int d = 1; d < n; d <<= 1) {
        for (int m = d << 1, i = 0; i < n; i += m) {
            for (int j = 0; j < d; ++j) {
                if (!inv)
                    a[i + j] += a[i + j + d];
                else
                    a[i + j] -= a[i + j + d];
            }
        }
    }
}

XOR 卷积

$\mathrm{xor}$ 卷积的构造相比前两个更加麻烦。

设序列 $X$（长为 $n$）的中间态为 $\mathrm{FWT}(X)$，其中

$$\mathrm{FWT}(X{)}_k=\sum _{i=0}^{n-1}f(i,k)X_i$$

其中 $f(x,$$y)$ 是待确定的函数，需要通过以下过程反推出来。

---

要使 $\mathrm{FWT}(A{)}_k\times \mathrm{FWT}(B{)}_k=$$\mathrm{FWT}(C{)}_k$，即

$$\sum _{i=0}^{n-1}f(i,k)A_i\times \sum _{j=0}^{n-1}f(j,k)B_j=\sum _{x=0}^{n-1}f(x,k)C_x$$

将 $C_x=$$\sum _{i\mathrm{xor}j=x}{A}_i{B}_j$ 代入

$$\sum _{i=0}^{n-1}f(i,k)A_i\times \sum _{j=0}^{n-1}f(j,k)B_j=\sum _{x=0}^{n-1}f(x,k)\sum _{i\mathrm{xor}j=x}{A}_i{B}_j$$$$\sum _{i=0}^{n-1}\sum _{j=0}^{n-1}f(i,k)f(j,k)A_i{B}_j=\sum _{x=0}^{n-1}\sum _{i\mathrm{xor}j=x}f(x,k)A_i{B}_j$$

在 $0\cdots n-$$1$ 范围内，对于每个可能的 $i,$$j$ 组合，总有一个 $x$ 满足 $i\mathrm{xor}j=$$x$，所以 $\sum _{x=0}^{n-1}\sum _{i\mathrm{xor}j=x}$ 实际上遍历了所有的 $i$ 和 $j$，因此

$$\sum _{i=0}^{n-1}\sum _{j=0}^{n-1}f(i,k)f(j,k)A_i{B}_j=\sum _{i=0}^{n-1}\sum _{j=0}^{n-1}f(i\mathrm{xor}j,k)A_i{B}_j$$

即得

$$\begin{array}{}\text{(i)}& f(i,k)f(j,k)=f(i\mathrm{xor}j,k)\end{array}$$

---

注意到

$$\begin{array}{}\text{(ii)}& a\mathrm{xor}b=c\Rightarrow (-1{)}^{\mathrm{bitcount}(a)}(-1{)}^{\mathrm{bitcount}(b)}=(-1{)}^{\mathrm{bitcount}(c)}\end{array}$$

其中 $\mathrm{bitcount}(x)$ 表示 $x$ 的二进制中 $1$ 的个数。

TIP

$(\mathrm{ii})$ 式是在说：$a\mathrm{xor}b=$$c$，$\mathrm{bitcount}(a)+$$\mathrm{bitcount}(b)$ 的奇偶性和 $\mathrm{bitcount}(c)$ 相同。

这个结论是显然的。在二进制按位异或的过程中：

• 若 $a,$$b$ 当前位均为 $1$，则 $c$ 的该位为 $0$，相当于少了两个 $1$，$\mathrm{bitcount}$ 的奇偶性没变；
• 若一个是 $1$，另一个是 $0$，则 $c$ 的该位为 $1$，相当于没差；
• 若都是 $0$ 也没差。

既然奇偶性相同，那么 $(-$$1{)}^{\mathrm{bitcount}(a)+\mathrm{bitcount}(b)}=$$(-$$1{)}^{\mathrm{bitcount}(c)}$，变形可得 $(\mathrm{ii})$ 式。

又注意到

$$(i\mathrm{and}k)\mathrm{xor}(j\mathrm{and}k)=(i\mathrm{xor}j)\mathrm{and}k$$

代入 $(\mathrm{ii})$ 式得

$$(-1{)}^{\mathrm{bitcount}(i\mathrm{and}k)}(-1{)}^{\mathrm{bitcount}(j\mathrm{and}k)}=(-1{)}^{\mathrm{bitcount}((i\mathrm{xor}j)\mathrm{and}k)}$$

于是便可以确定函数 $f$ 的形式：

$$f(x,y)=(-1{)}^{\mathrm{bitcount}(x\mathrm{and}y)}$$

该形式完美符合 $(\mathrm{i})$ 式的结论。

从而序列 $X$ 的中间态的全貌应该是这样的：

$$\mathrm{FWT}(X{)}_k=\sum _{i=0}^{n-1}(-1{)}^{\mathrm{bitcount}(i\mathrm{and}k)}{X}_i$$

---

现对 $\mathrm{FWT}(A{)}_k$ 进行分治。

• 当 $0\le k\le \frac{n}{2}-$$1$ 时，直接把求和式拆分成两半：$$\begin{array}{rl}\mathrm{FWT}(A{)}_k& =\sum _{i=0}^{n-1}(-1{)}^{\mathrm{bitcount}(i\mathrm{and}k)}{A}_i\\ & =\sum _{i=0}^{\frac{n}{2}-1}(-1{)}^{\mathrm{bitcount}(i\mathrm{and}k)}{A}_i+\sum _{i=\frac{n}{2}}^{n-1}(-1{)}^{\mathrm{bitcount}(i\mathrm{and}k)}{A}_i\\ & =\sum _{i=0}^{\frac{n}{2}-1}(-1{)}^{\mathrm{bitcount}(i\mathrm{and}k)}(A_{\mathrm{prev}}{)}_i+\sum _{i=0}^{\frac{n}{2}-1}(-1{)}^{\mathrm{bitcount}(i\mathrm{and}k)}(A_{\mathrm{back}}{)}_i\\ & =\mathrm{FWT}(A_{\mathrm{prev}}{)}_k+\mathrm{FWT}(A_{\mathrm{back}}{)}_k\end{array}$$
• 当 $\frac{n}{2}\le k\le n-$$1$ 时，需要对下标 $k$ 进行偏移，偏移量为 $\frac{n}{2}$，理由同 OR 卷积。 需要注意的是，当 $i$ 取 $\frac{n}{2}\cdots n-$$1$ 时，$\mathrm{bitcount}\left(i\mathrm{and}(k-\frac{n}{2})\right)=$$-$$\mathrm{bitcount}(i\mathrm{and}k)$，下标偏移导致了此处符号的改变。$$\begin{array}{rl}\mathrm{FWT}(A{)}_k& =\sum _{i=0}^{n-1}(-1{)}^{\mathrm{bitcount}(i\mathrm{and}k)}{A}_i\\ & =\sum _{i=0}^{\frac{n}{2}-1}(-1{)}^{\mathrm{bitcount}\left(i\mathrm{and}(k-\frac{n}{2})\right)}{A}_i-\sum _{i=\frac{n}{2}}^{n-1}(-1{)}^{\mathrm{bitcount}\left(i\mathrm{and}(k-\frac{n}{2})\right)}{A}_i\\ & =\sum _{i=0}^{\frac{n}{2}-1}(-1{)}^{\mathrm{bitcount}\left(i\mathrm{and}(k-\frac{n}{2})\right)}(A_{\mathrm{prev}}{)}_i-\sum _{i=0}^{\frac{n}{2}-1}(-1{)}^{\mathrm{bitcount}\left(i\mathrm{and}(k-\frac{n}{2})\right)}(A_{\mathrm{back}}{)}_i\\ & =\mathrm{FWT}(A_{\mathrm{prev}}{)}_{k-\frac{n}{2}}-\mathrm{FWT}(A_{\mathrm{back}}{)}_{k-\frac{n}{2}}\end{array}$$

即

$$\mathrm{FWT}(A{)}_k=\{\begin{array}{ll}\mathrm{FWT}(A_{\mathrm{prev}}{)}_k+\mathrm{FWT}(A_{\mathrm{back}}{)}_k,& 0\le k\le \frac{n}{2}-1\\ \\ \mathrm{FWT}(A_{\mathrm{prev}}{)}_{k-\frac{n}{2}}-\mathrm{FWT}(A_{\mathrm{back}}{)}_{k-\frac{n}{2}},& \frac{n}{2}\le k\le n-1\end{array}$$

进一步地

$$\mathrm{FWT}(A)=\{\begin{array}{ll}A,& n=1\\ \mathrm{merge}(\mathrm{FWT}(A_{\mathrm{prev}})\oplus \mathrm{FWT}(A_{\mathrm{back}}),\mathrm{FWT}(A_{\mathrm{prev}})\ominus \mathrm{FWT}(A_{\mathrm{back}})),& n>1\end{array}$$

对应地

$$\mathrm{UFWT}(A)=\{\begin{array}{ll}A,& n=1\\ \mathrm{merge}\left({\displaystyle \frac{\mathrm{UFWT}(A_{\mathrm{prev}})\oplus \mathrm{UFWT}(A_{\mathrm{back}})}{2},\frac{\mathrm{UFWT}(A_{\mathrm{prev}})\ominus \mathrm{UFWT}(A_{\mathrm{back}})}{2}}\right),& n>1\end{array}$$

其中对序列的除法运算也是点对点除法。

模板

void FWT_XOR(vector<int>& a, int l, int r, bool inv) {
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    FWT_XOR(a, l, mid, inv);
    FWT_XOR(a, mid + 1, r, inv);
    for (int i = 0; i <= mid - l; i ++) {
        int u = a[l + i], v = a[mid + 1 + i];
        a[l + i] = u + v;
        a[mid + 1 + i] = u - v;
    }
    if (inv) {
        for (int i = l; i <= r; i ++) {
            a[i] /= 2;
        }
    }
}

void FWT_XOR(vector<int>& a, bool inv) {
    int n = a.size();
    for (int d = 1; d < n; d <<= 1) {
        for (int i = 0; i < n; i += (d << 1)) {
            for (int j = 0; j < d; j ++) {
                int u = a[i + j], v = a[i + j + d];
                a[i + j] = u + v;
                a[i + j + d] = u - v;
            }
        }
    }
    if (inv) {
        for (int i = 0; i < n; i ++) {
            a[i] /= n;
        }
    }
}