为了实现 FWT，我们需要实现所谓带权前缀和。
具体来说，给定序列 \(\{A\}_{i=0}^{c^n-1}\)（这里我们推广了一般的二进制情况），以及一个函数 \(w(i,j)\quad i \in [0,d^n),j\in [0,c^n)\)，我们需要求出：
我们记 \(x^{(y)}_z\) 表示 \(x\) 在 \(y\) 进制下的第 \(z+1\) 位。
当上下文语意明确时，我们省略上标。
一般为了方便求解，\(w\) 有性质：
好的，怎么求解这个一般的 FWT 呢？
这里有一个问题，我们输入的下标是 \(c\) 进制的，而输出是 \(d\) 进制的，这似乎并不相容。
所以第一步就是统一进制，加入一些空的位置。
令 \(\textup{tran}_{x}^{y}(i)\) 表示若 \(i=(a_1\dots a_l)_x\)，则 \(\textup{tran}_{x}^{y}(i)=(a_1\dots a_l)_y\)。（我们忽略一些合法性检查）
分讨：
- \(c=d\)：什么也不用做。
- \(c>d\)：我们构造新函数 \(w^{\prime}(\textup{tran}_d^c(i),j)=w(i,j)\)，剩下的填 \(0\)，记使用 \(w^{\prime}\) 得到的序列为 \(B^{\prime}\)，最后 \(\textup{FWT}(A)_i=B^{\prime}_{\textup{tran}_d^c(i)}\)。
- \(c<d\)：我们构造 \(A^{\prime}_{\textup{tran}_c^d(i)}=A_i,w^{\prime}(i,\textup{tran}_c^d(j))=w(i,j)\)，剩下的填 \(0\)。
总之，现在统一了进制，以下假设 \(c=d\)。
接下来，我们依次考虑每一位 \(0\le i<n\)，令 \(A^{[i]}_k=\sum\limits_{\lfloor j/c^t \rfloor=\lfloor i/c^t \rfloor}w(k,j)A_j\)。
由于 \(w\) 每一维是独立的，因此依照 \(w(k_i,j_i)\) 分配就可以了。
可能不是很明了，我们举一个例子：
这里 \(w(i,j)=W_{ij}\)（下标从 \(0\) 开始）。
那么代码实现大概是这样（这里直接原地操作）：
void FWT(int n,int* A){for(int k=0;k<n;++k){for(int i=0;i<(1<<n);i+=(1<<(k+1))){for(int j=0;j<(1<<k);++j){int tmp=A[i|j];A[i|j]=A[i|j]+A[i|j|(1<<k)];A[i|j|(1<<k)]=tmp-A[i|j|(1<<k)];}}}
}
至于完整的实现，一般用不着，就不给出了。
接下来考虑做卷积。
卷积就是 \(C_k=\sum_{i\textup{ op }j=k}A_iB_j\)。
其中 \(\textup{op}\) 是一个位运算，也就是说各位独立。