Loading...

FWT (伪)学习笔记

check评论:0 条 remove_red_eye浏览量:396 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2019-01-23

其实就是一份代码合集

$FFT$和$NTT$我们来解决形如$C_k =\sum\limits_{i+j=k} A_iB_j$一类的卷积问题,但是如果底下换成了位运算,就要用$FWT$

基于$FFT$的思想,我们需要在$O(nlogn)$时间内将数组$A$转化为另一个数组$FWT(A)$,使得$FWT(C)=FWT(A)*FWT(B)$就行了

然后关于其他的推导啊啥的就先鸽了先放代码吧qaq

回头再填坑

例题:洛谷P4717 [模板]快速沃尔什变换

#include <bits/stdc++.h>
using namespace std;
#define mod 998244353
#define inv 499122177
long long a[(2<<17)+10],b[(2<<17)+10];
long long c[(2<<17)+10];
int n;
void FWT_or(long long x[],int flag)
{
    for(int mid=1;mid<n;mid<<=1)
    {
        for(int r=(mid<<1),i=0;i<n;i+=r)
        {
            for(int k=0;k<mid;k++)
            {
                if(flag)
                {
                    x[i+mid+k]+=x[i+k];
                    x[i+mid+k]%=mod;
                }
                else
                {
                    x[i+mid+k]=(x[i+mid+k]-x[i+k]+mod)%mod;
                }
            }
        }
    }
}
void FWT_and(long long x[],int flag)
{
    for(int mid=1;mid<n;mid<<=1)
    {
        for(int r=(mid<<1),i=0;i<n;i+=r)
        {
            for(int k=0;k<mid;k++)
            {
                if(flag)
                {
                    x[i+k]+=x[i+mid+k];
                    x[i+k]%=mod;
                }
                else
                {
                    x[i+k]=(x[i+k]-x[i+mid+k]+mod)%mod;
                }
            }
        }
    }
}
void FWT_xor(long long x[],int flag)
{
    for(int mid=1;mid<n;mid<<=1)
    {
        for(int r=(mid<<1),i=0;i<n;i+=r)
        {
            for(int k=0;k<mid;k++)
            {
                long long qaq=x[i+k],qwq=x[i+mid+k];
                x[i+k]=(qaq+qwq)%mod;
                x[i+mid+k]=(qaq-qwq+mod)%mod;
                if(!flag)
                {
                    x[i+k]=x[i+k]*inv%mod;
                    x[i+mid+k]=x[i+mid+k]*inv%mod;
                }
            }
        }
    }
}
int main()
{
    cin>>n;
    n=(1<<n);
    for(int i=0;i<n;i++)
    {
        scanf("%lld",&a[i]);
    }
    for(int i=0;i<n;i++)
    {
        scanf("%lld",&b[i]);
    }
    FWT_or(a,1),FWT_or(b,1);
    for(int i=0;i<n;i++)
    {
        c[i]=a[i]*b[i]%mod;
    }
    FWT_or(a,0),FWT_or(b,0),FWT_or(c,0);
    for(int i=0;i<n;i++)
    {
        printf("%lld ",c[i]);
    }
    cout<<endl;
    FWT_and(a,1),FWT_and(b,1);
    for(int i=0;i<n;i++)
    {
        c[i]=a[i]*b[i]%mod;
    }
    FWT_and(a,0),FWT_and(b,0),FWT_and(c,0);
    for(int i=0;i<n;i++)
    {
        printf("%lld ",c[i]);
    }
    cout<<endl;
    FWT_xor(a,1),FWT_xor(b,1);
    for(int i=0;i<n;i++)
    {
        c[i]=a[i]*b[i]%mod;
    }
    FWT_xor(a,0),FWT_xor(b,0),FWT_xor(c,0);
    for(int i=0;i<n;i++)
    {
        printf("%lld ",c[i]);
    }
} 

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名