另一个视角下的 FWT

一般的 FWT 的解释是直接利用分治和一些注意力注意到了一个变换方法。但是这个方法怎么来的，或者将题目变换以下，一般的解释就无能为力了。

此处提供另一种解释。

不妨假设我们要变换的数组为 $f$ ，变换的结果为 $F$ 。

设 $F_i=\sum_{j=0}^{n-1} c(i,j)f_j$ 。

那么，容易发现，如果说卷积运算符为 $\oplus$ ，那么只要满足 $c(i,j)c(i,k)=c(i,j\oplus k)$ ，那么卷积就一定可以表示为这种变换后的结果的点乘。

那么问题就是如何作这种变换。

以二进制位运算卷积举例，我们可以发现一些性质：

$F_i=\sum_{j=0}^{n-1} c(i,j)f_j=\sum_{j=0}^{\frac{n}{2}-1}c(i,j)f_j+\sum_{j=\frac{n}{2}}^{n-1}c(i,j)f_j$ 。

如果说 $i$ 的最高位为 $i_0$ ，去掉最高位后为 $i_1$ ，那么就有：

$F_i=c(i_0,0)\sum_{j=0}^{\frac{n}{2}-1}c(i_1,j)f_j+c(i_0,1)\sum_{j=\frac{n}{2}}^{n-1}c(i_1,j)f_j$

这个过程可以分治进行，于是我们也得到了 FWT 位运算卷积算法。

如果说我们把 $c(i,j)$ 看成矩阵 $C$ ，那么对 $C$ 求逆后的矩阵 $C'$ 进行 FWT 运算就可以还原 FWT 变换结果了。

例如或卷积，我们就有矩阵：

$$\begin{bmatrix} 1 & 0\\ 1&1 \end{bmatrix}$$

以及求逆后的矩阵：

$$\begin{bmatrix} 1 & 0\\ -1&1 \end{bmatrix}$$

可以发现这个和我们平常的 FWT 得到的结果是一摸一样的。

HDU20260806G Multician

场切了。

题目描述：

定义 $i\oplus j$ 为 $6$ 进制下不进位乘法的结果。

给定长度为 $6^n$ 的序列 $a,b$ ，求 $\oplus$ 卷积的结果 $c$ 。

这题可以直接 FWT 。

注意到

$$\begin{bmatrix} 1&1&1&1&1&1\\ 0&1&0&0&0&1\\ 0&1&0&0&0&-1\\ 0&1&0&1&0&1\\ 0&1&1&0&1&1\\ 0&1&-1&0&1&-1 \end{bmatrix}$$

满足条件且可逆，于是求逆后直接按照上面的步骤 FWT 就行。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=2100010,P=100000007;
const int a[6][6]={
    1,1,1,1,1,1,
    0,1,0,0,0,1,
    0,1,0,0,0,100000006,
    0,1,0,1,0,1,
    0,1,1,0,1,1,
    0,1,100000006,0,1,100000006
};
const int b[6][6]={
    1,1,0,100000006,100000006,0,
    0,50000004,50000004,0,0,0,
    0,50000003,50000004,0,50000004,50000003,
    0,100000006,0,1,0,0,
    0,50000003,50000003,0,50000004,50000004,
    0,50000004,50000003,0,0,0
};
namespace IO
{
    constexpr int S = 1 << 20;
    char b1[S], *p1, *p2;
    char b2[S], *p3 = b2;
    
    #define G (p1 == p2 && (p2 = (p1 = b1) + fread(b1, 1, S, stdin)), *p1 ++)
    #define P (p3 == b2 + S && (p3 = b2, fwrite(b2, S, 1, stdout)), *p3 ++)

    int R()
    {
        int x = 0, c = G;
        while (!isdigit(c)) c = G;
        while (isdigit(c)) x = x * 10 + (c & 15), c = G;
        return x;
    }

    void W(int x, char c)
    {
        static char stk[10]; int top = 0;
        do stk[top ++] = x % 10 | '0', x /= 10; while (x);
        while (top --) P = stk[top];
        P = c;
    }

    void flush() {fwrite(b2, p3 - b2, 1, stdout), p3 = b2;}

    #undef G
    #undef P
}
int n,A[N],B[N],lim,t[6];
void FWT(int *A){
    for(int i=6;i<=lim;i*=6){
        for(int j=0;j<lim;j+=i){
            for(int k=0;k<i/6;k++){
                for(int l=0;l<6;l++)t[l]=A[j+k+l*i/6];
                for(int l=0;l<6;l++){
                    A[j+k+l*i/6]=0;
                    for(int p=0;p<6;p++)
                        (A[j+k+l*i/6]+=1ll*a[l][p]*t[p]%P)%=P;
                }
            }
        }
    }
}
void IFWT(int *A){
    for(int i=6;i<=lim;i*=6){
        for(int j=0;j<lim;j+=i){
            for(int k=0;k<i/6;k++){
                for(int l=0;l<6;l++)t[l]=A[j+k+l*i/6];
                for(int l=0;l<6;l++){
                    A[j+k+l*i/6]=0;
                    for(int p=0;p<6;p++)
                        (A[j+k+l*i/6]+=1ll*b[l][p]*t[p]%P)%=P;
                }
            }
        }
    }
}
void WZH(){
   n=IO::R();
    lim=1;
    for(int i=1;i<=n;i++)lim*=6;
    for(int i=0;i<lim;i++)A[i]=IO::R();
    for(int i=0;i<lim;i++)B[i]=IO::R();
    FWT(A);FWT(B);
    for(int i=0;i<lim;i++)A[i]=1ll*A[i]*B[i]%P;
    IFWT(A);
    for(int i=0;i<lim;i++)IO::W(A[i]," \n"[i==lim-1]);
    // for(int i=0;i<lim;i++)printf("%d ",A[i]);puts("");
}
int main(){
    int T;
   T=IO::R();
    while(T--)WZH();
   IO::flush();
    return 0;
}