能轻松背板子的FWT(快速沃尔什变换)
FWT应用
FWT(Fast Walsh Fransform),中文名快速沃尔什变换 (FFT)当然可以做多项式卷积 但是如果把(i+j)换一下操作符 结论类似(FFT),把当前多项式(A)拆成前一半(A_0)和后一半(A_1)
[FWT(A)=merge(FWT(A_0),FWT(A_0)+FWT(A_1))] [IFWT(A)=merge(IFWT(A_0),IFWT(A_0)-IFWT(A_1))]
[FWT(A)=merge(FWT(A_0)+FWT(A_1),FWT(A_1))] [IFWT(A)=merge(IFWT(A_0)-IFWT(A_1),IFWT(A_1))]
[FWT(A)=merge(FWT(A_0)+FWT(A_1),FWT(A_0)-FWT(A_1))] [IFWT(A)=merge({{IFWT(A_0)+IWFT(A_1)}over 2},{IFWT(A_0)-IFWT(A_1)over 2})] (+)就是每一位值加起来,不知道(merge)是什么东西? 原理
令(FWT(A)=A',A'[i]=sum_{i|j=i}A[j]),(B)同理 肯定不能枚举(i)的二进制子集因为太沙雕 设当前多项式(A)的长度为(2^k),(A_0,A_1)长度为(2^{k-1}) 至于(IFWT),就是已知(A_0',A_1'),求(A_0,A_1) 对于(and)也可同理推一波操作,和(or)很像,结论、代码也很像
一看(or)和(and)的结论就很清真,其实是因为(or)和(and)很像 令(i&;j)中(1)数量的奇偶性为(i)与(j)的奇偶性,那么(i)与(k)的奇偶性异或(j)和(k)的奇偶性等于(i⊕j)和(k)的奇偶性 如果这样的话 [IFWT(A)=merge({{IFWT(A_1)-IWFT(A_0)}over 2},{IFWT(A_1)+IFWT(A_0)over 2})] FWT板子#define mod 998244353 #define inv2 499122177 inline void fwt_or(ll f[],ll len,ll inv) { for (ll i=1;i<len;i<<=1) for (ll j=0;j<len;j+=(i<<1)) for (ll k=0;k<i;++k) f[i+j+k]=(inv*f[j+k]+f[i+j+k]+mod)%mod; } inline void fwt_and(ll f[],ll inv) { for (ll i=1;i<len;i<<=1) for (ll j=0;j<len;j+=(i<<1)) for (ll k=0;k<i;++k) f[j+k]=(f[j+k]+inv*f[i+j+k]+mod)%mod; } inline void fwt_xor(ll f[],ll inv) { for (ll i=1;i<len;i<<=1) for (ll j=0;j<len;j+=(i<<1)) for (ll k=0;k<i;++k) { ll x=f[j+k],y=f[i+j+k]; f[j+k]=(x+y)%mod,f[i+j+k]=(x-y+mod)%mod; if (inv==-1)(f[j+k]*=inv2)%=mod,(f[i+j+k]*=inv2)%=mod; } } FWT搞完
别人早就会的东西我现在才学 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |