能看到这篇博客的人,一定知道FWT是干什么的。(什么?你不知道?)
没事,这里有pick讲FWT的博客。先点进去看一看。
如果你看懂了,那么恭喜你。如果你跟我一样看不懂,那么请继续往下看。

这里的A和B都是什么呢?其实它们是一个多维的向量(如果你不知道向量是什么,就把它当成数组),下标从0开始。
其中,$ A = <a_{0},a_{1},...,a_{2^{k}-1}> $,$ B = <b_{0},b_{1},...,b_{2^{k}-1}> $,$ C = A\otimes B $
这里我们定义$$ A\pm B = < a_{0}\pm b_{0}, a_{1}\pm b_{1},..., (a_{2^{k}-1})\pm (b_{2^{k}-1}) > $$ 即对应位相加(减)$$ A * B = < a_{0} * b_{0}, a_{1} * b_{1},..., (a_{2^{k}-1}) * (b_{2^{k}-1}) > $$即对应位相乘$ A\otimes B $ 为A和B做卷积之后得到的结果,也是一个和原来大小一样的向量。

注意到FWT做的是二进制上的位运算,所以一定要把A和B补到2的整次幂次(即不足的地方填上0)。

我们要构造一个变换tf,使得$tf(A)*tf(B)=tf(C)$。这个变换的对象是一个大小为$2^{k}$的向量,变换出来的结果也是一个大小为$2^{k}$的向量。

就以异或举例。picks告诉我们$$tf(A)=(tf(A_{0})+tf(A_{1}),tf(A_{0})-tf(A_{1}))$$$$A_{0}=<a_{0},a_{1},...,a_{2^{k-1}-1}>$$$$A_{1}=<a_{2^{k-1}},a_{2^{k-1}+1},...,a_{2^{k}-1}>$$即把A中的下标按照二进制最高位为0或1分成前后两部分(前面的为$A_{0}$,后面的为$A_{1}$),分治下去做。

分治之后得到$tf(A_{0})$和$tf(A_{1})$。然后tf(A)的前半部分(即$[0,2^{k-1}-1]$)为$tf(A_{0})+tf(A_{1})$,后半部分(即$[2^{k-1},2^{k}-1]$)为$tf(A_{0})-tf(A_{1})$。(其实就是已知两个向量,把两个向量做加减运算,加的那个结果填到前一半中,减的那个结果填到后一半中)。

然而,这为什么是对的?
接下来我们来证明它是对的。

我要事先说明(注意不是证明)一个引理:$tf(A+B)=tf(A)+tf(B)$。这个东西看上去挺直观的(一点都不直观好吗。。)。这个东西可以用数学归纳法证。这里略过。。。(有时间的时候再补上)

我们看k=1的时候。根据定义,有$$tf(A)=<a_{0}+a_{1},a_{0}-a_{1}>$$$$tf(B)=<b_{0}+b_{1},b_{0}-b_{1}>$$$$tf(C)=<c_{0}+c_{1},c_{0}-c_{1}>$$$$c_{0}=a_{0}*b_{0}+a_{1}*b_{1},c_{1}=a_{0}*b_{1}+a_{1}*b_{0}$$自己代代看,反正代出来很神奇的的发现$tf(A)*tf(B)=tf(C)$

接下来使用数学归纳法。假设对于大小都为$2^{k}(k\epsilon N)$的向量A和B,满足$C = A\otimes B$,并且$tf(A)*tf(B)=tf(C)$。
考虑当大小为$2^{k+1}$的情况。我们要证明在这种情况下,$tf(A)*tf(B)=tf(C)$。根据定义,有
$$tf(A)=(tf(A_{0})+tf(A_{1}),tf(A_{0})-tf(A_{1}))$$$$tf(B)=(tf(B_{0})+tf(B_{1}),tf(B_{0})-tf(B_{1}))$$$$tf(A)*tf(B)=([tf(A_{0})+tf(A_{1})]*[tf(B_{0})+tf(B_{1})],[tf(A_{0})-tf(A_{1})]*[tf(B_{0})-tf(B_{1})])$$
暴力把式子拆开,有
$tf(A)*tf(B)=$
$$(tf(A_{0})*tf(B_{0})+tf(A_{0})*tf(B_{1})+tf(A_{1})*tf(B_{0})+tf(A_{1})*tf(B_{1}),$$$$tf(A_{0})*tf(B_{0})+tf(A_{1})*tf(B_{1})-tf(A_{0})*tf(B_{1})-tf(A_{1})*tf(B_{0}))$$
注意到这里的$A_{0}$,$A_{1}$,$B_{0}$,$B_{1}$都是大小为$2^{k}$的向量,符合归纳的基础。于是,
$tf(A)*tf(B)=$
$$(tf(A_{0}\otimes B_{0})+tf(A_{0}\otimes B_{1})+tf(A_{1}\otimes B_{0})+tf(A_{1}\otimes B_{1}),$$$$tf(A_{0}\otimes B_{0})+tf(A_{1}\otimes B_{1})-tf(A_{0}\otimes B_{1})-tf(A_{1}\otimes B_{0}))$$
由于异或每一位是独立,而这里如果我们把C按照最高位为0或1分成两部分,最高位的异或和其它位不相关。
于是有$$C=(C_{0},C_{1})=(A_{0}\otimes B_{0}+A_{1}\otimes B_{1},A_{0}\otimes B_{1}+A_{1}\otimes B_{0})$$
要证的等式
$$右边=tf(C)=tf(C_{0},C_{1})$$$$=tf(A_{0}\otimes B_{0}+A_{1}\otimes B_{1},A_{0}\otimes B_{1}+A_{1}\otimes B_{0})$$$$=(tf(A_{0}\otimes B_{0}+A_{1}\otimes B_{1})+tf(A_{0}\otimes B_{1}+A_{1}\otimes B_{0}),tf(A_{0}\otimes B_{0}+A_{1}\otimes B_{1})-tf(A_{0}\otimes B_{1}+A_{1}\otimes B_{0}))$$$$=(tf(A_{0}\otimes B_{0})+tf(A_{1}\otimes B_{1})+tf(A_{0}\otimes B_{1})+tf(A_{1}\otimes B_{0}),tf(A_{0}\otimes B_{0})+tf(A_{1}\otimes B_{1})-tf(A_{0}\otimes B_{1})-tf(A_{1}\otimes B_{0}))$$$$=tf(A)*tf(B)=左边$$
至此,证毕。

然而这只是一个tf,还有一个逆变换utf。这个逆变换的正确性可以用同样的方法证明,即先看k=1的情况,然后一步一步用数归推上去。
证明方法比较简单(真的很简单),这里略过。

至于其它位运算,其证明方法与异或一致,这里不赘述。

说了这么多,其实这个证明并没有什么卵用(只是使得自己相信它是对的)。。大家还是背代码吧。。。

看完的找个模板题练练手感受一下吧,CSU 1911 Card Game

模板

// 题目要求取模时使用mod,否则去除mod
void FWT(int a[], int n)
{
    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++) {
                int x = a[i + j];
                int y = a[i + j + d];
                a[i + j] = (x + y) % mod;
                a[i + j + d] = (x - y + mod) % mod;
                // xor: a[i+j]=x+y, a[i+j+d]=x-y;
                // and: a[i+j]=x+y;
                // or: a[i+j+d]=x+y;
            }
        }
    }
}
void UFWT(int a[], int n)
{
    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++) {
                int x = a[i + j];
                int y = a[i + j + d];
                a[i + j] = 1LL * (x + y) * rev % mod;
                a[i + j + d] = (1LL * (x - y) * rev % mod + mod) % mod;
                // xor: a[i+j]=(x+y)/2, a[i+j+d]=(x-y)/2;
                // and: a[i+j]=x-y;
                // or: a[i+j+d]=y-x;
            }
        }
    }
}
void solve(int a[], int b[], int n)
{
    FWT(a, n);
    FWT(b, n);
    for (int i = 0; i < n; i++) {
        a[i] = 1LL * a[i] * b[i] % mod;
    }
    UFWT(a, n);
}
最后修改:2020 年 06 月 17 日 05 : 33 PM
如果觉得我的文章对你有用,请随意赞赏