给定\(F(a_0,a_1...a_n)_3\)，\(G(a_0,a_1...a_n)_3\)
定义\(a \oplus b\) 为3进制不进位加法，求$ Ans= F \oplus G$ ，即求
\[Ans(a_0+b_0 \bmod 3,a_1+b_1 \bmod 3,...,a_n+b_n \bmod 3)_3=F(a_0,a_1...a_n)_3 G(b_0,b_1...b_n)_3\]
part 1
我们先考虑\(n\)为\(1\)的情况，可以发现这就是一个长度为\(3\)的循环卷积。
因为该卷积的元素个数很少，我们考虑如何对多项式\(A(x)\)暴力求\(DFT(A(x))\)和\(IDFT(A(x))\)。
回想一下\(DFT\)是在做什么，它相当于是给定多项式\(A(x)\)各位的系数\(a_i\)，对多项式\(A(x)\)求\(x=\omega_n^0,\omega_n^1...\omega_n^{n-1}\)时的值。
\(IDFT\)就是给定多项式\(A(x)\)在\(x=\omega_n^0,\omega_n^1...\omega_n^{n-1}\) 的值，求多项式\(A(x)\)各位的系数\(a_i\)。
考虑一下以下矩阵(范德蒙德矩阵)
\[T_n =\begin{bmatrix}1 & 1 & 1 & \ldots & 1 \\1 & \omega_n ^ 1 & \omega_n ^ 2 & \ldots & \omega_n ^ {n - 1} \\1 & \omega_n ^ 2 & \omega_n ^ 4 & \ldots & \omega_n ^ {2(n - 1)} \\\ldots & \ldots & \ldots & \ddots & \ldots \\1 & \omega_n ^ {n - 1} & \omega_n ^ {2(n - 1)} & \ldots & \omega_n ^ {(n - 1)(n - 1)} \\\end{bmatrix}\]
我们发现对\(A(x)\)求\(DFT\)就是对\(A(x)\)所表示的向量乘上矩阵\(T_n\)
考虑\(T_n\)的逆矩阵
\[T_n ^ {-1} = \frac{1}{n}\begin{bmatrix}1 & 1 & 1 & \ldots & 1 \\1 & \omega_n ^ {-1} & \omega_n ^ {-2} & \ldots & \omega_n ^ {-(n - 1)} \\1 & \omega_n ^ {-2} & \omega_n ^ {-4} & \ldots & \omega_n ^ {-2(n - 1)} \\\ldots & \ldots & \ldots & \ddots & \ldots \\1 & \omega_n ^ {-(n - 1)} & \omega_n ^ {-2(n - 1)} & \ldots & \omega_n ^ {-(n - 1)(n - 1)} \\\end{bmatrix}\]
可以证明该矩阵是\(T_n\)的逆矩阵()
那么对\(A(x)\)求\(IDFT\)就是对\(A(x)\)所表示的向量乘上矩阵\(T_n^{-1}\)
对于一个大小为\(3\)的多项式，我们只要先求出\(3\)次单位根，再暴力乘上一个\(3*3\)的矩阵就好了
Part 2
若\(n>1\)，那么我们要求一下式子(为了方便以下式子都省略\(\bmod 3\))
\[F(a_0,a_1...a_n)_3 G(b_0,b_1...b_n)_3 \to Ans(a_0+b_0,a_1+b_1,...,a_n+b_n)_3\]
我们不妨先枚举\(a_1,a_2...a_n,b_1,b_2...b_n\)，
\[F(a_0,x,y...z)_3 G(b_0,u,v...w)_3 \to Ans(a_0+b_0,x+u,y+v,...,z+w)_3\]
我们此时只要对\(F,G\)的第一维做循环卷积就好了。
假设我们已经对\(F(a_0,x,y...z)\)和\(G(b_0,u,v...w)\)的第一维做了\(DFT\)变换
此时我们要求:
\[F(X,x,y...z)_3 G(X,u,v...w)_3 \to Ans(X,x+u,y+v,...,z+w)_3\]
然后再对 \(Ans\) 的第一维做\(IDFT\)变换
我们考虑求解它的一个子问题
\[F(X,x,y...z)_3 G(X,u,v...w)_3 \to Ans(X,x+u,y+v,...,z+w)_3\]
即枚举\(F,G\)的第一维，再枚举\(F,G\)除第二维以后的后面几维
\[F(X,a_1,x,y...z)_3 G(X,b_1,u,v...w)_3 \to Ans(X,a_1+b_1,x+u,y+v,...,z+w)_3\]
我们发现这个形式和上面的形式差不多，我们此时再对\(F,G\)第二维做\(DFT\)变换，再解决一个子问题，再对\(Ans\)
第二维做\(IDFT\)变换
我们这样递归下去，发现我们就是对\(F,G\)的\(1 \to n\)维做\(DFT\)变换，再对\(F,G\) 对应的点值相乘，再做\(IDFT\)变换
伪代码:
FWT(A),FWT(B)
for(i=0~(3^n)-1) A[i]*B[i]->Ans[i]
IFWT(Ans)复杂度\(O(3^n n *3^2)\)
若将\(3\)换成\(d\)，复杂度为\(O(d^n n* d^2)\)或\(O(d^n n* d logd)\)