• 周四. 10 月 3rd, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

集合幂级数笔记

admin

11 月 28, 2021

快速沃尔什变换
(hat{f_{S}} = sum_{T} (-1)^{| S & T |} f_{T})

代码

for (int i=0; i<p; ++i){
    int has=((1<<p)-1)^(1<<i);
    for (int j=has; j; j=(j-1)&has){
        int x=a[j],y=a[j+(1<<i)];
        a[j]=ADD(x,y);
        a[j+(1<<i)]=SUB(x,y);
    }
    int x=a[0],y=a[1<<i];
    a[0]=ADD(x,y);
    a[1<<i]=SUB(x,y);
}

逆 FWT 只需要FWT一遍后乘上 $ frac{1}{2^p}$

分治乘法好啊!

发表回复