FWT的板子

shadowice1984 · 2018-04-04 20:05:40 · 个人记录

这里是给shadowice1984自用的板子

所以详细的注释什么的是没有的………

tips:这个是异或卷积的板子，别的自己看公式好了

#include<cstdio>
#include<algorithm>
using namespace std;const int N=262160;typedef long long ll;
ll mod=1e9+7;const ll inv[3]={0,1,5*1e4+4};int n;int rn;int len;
inline void fwt(int* a,int tp)
{
    for(int k=1;k<n;k<<=1)
        for(int s=0;s<n;s+=k<<1)
            for(int i=s;i<s+k;i++)
            {
                ll a0=a[i];ll a1=a[i+k];
                a[i]=(a0+a1)*inv[tp]%mod;a[i+k]=(a0+mod-a1)*inv[tp]%mod;
            }
}