2020-2021:teams:legal_string:王智彪:fwt
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:legal_string:王智彪:fwt [2021/08/13 13:07] 王智彪 |
2020-2021:teams:legal_string:王智彪:fwt [2021/08/14 09:08] (当前版本) 王智彪 |
||
|---|---|---|---|
| 行 63: | 行 63: | ||
| $FWT(A+B)=FWT(A)+FWT(B)$ | $FWT(A+B)=FWT(A)+FWT(B)$ | ||
| - | $IFWT(A)=({\frac {IFWT(A_{0})-IFWT(A_{1})} 2},{\frac {IFWT(A_{0})-IFWT(A_{1})} 2})$ | + | $IFWT(A)=({\frac {IFWT(A_{0})+IFWT(A_{1})} 2},{\frac {IFWT(A_{0})-IFWT(A_{1})} 2})$ |
| + | |||
| + | $A_{i}=\sum_{C_{1}}A_{j}-\sum_{C_{2}}A_{j}$，（ $C_{1}$ 表示 $i\&j$ 奇偶性为 $0$ ，$C_{2}$ 表示奇偶性为 $1$ ，其中奇偶性代表二进制为 $1$ 的个数的奇偶性） | ||
| + | |||
| + | ==== 同或卷积 ==== | ||
| + | |||
| + | $FWT(A)=(FWT(A_{0})-FWT(A_{1}),FWT(A_{0})+FWT(A_{1}))$ | ||
| + | |||
| + | $FWT(A+B)=FWT(A)+FWT(B)$ | ||
| + | |||
| + | $IFWT(A)=({\frac {IFWT(A_{0})-IFWT(A_{1})} 2},{\frac {IFWT(A_{0})+IFWT(A_{1})} 2})$ | ||
| + | |||
| + | $A_{i}=\sum_{C_{1}}A_{j}-\sum_{C_{2}}A_{j}$，（ $C_{1}$ 表示 $i|j$ 奇偶性为 $0$ ，$C_{2}$ 表示奇偶性为 $1$ ，其中奇偶性代表二进制为 $1$ 的个数的奇偶性） | ||
| ===== 算法实现 ===== | ===== 算法实现 ===== | ||
| 行 101: | 行 113: | ||
| if(opt==-1)P[k]=1ll*P[k]*inv2%MOD,P[k+p]=1ll*P[k+p]*inv2%MOD; | if(opt==-1)P[k]=1ll*P[k]*inv2%MOD,P[k+p]=1ll*P[k+p]*inv2%MOD; | ||
| } | } | ||
| + | } | ||
| + | |||
| + | void tor_FWT(ll *P,int opt) {//同或卷积 | ||
| + | for(int i=2;i<=N;i<<=1) { | ||
| + | for(int p=i>>1,j=0;j<N;j+=i) { | ||
| + | for(int k=j;k<j+p;++k) { | ||
| + | ll x=P[k],y=P[k+p]; | ||
| + | P[k]=(x-y+MOD)%MOD; | ||
| + | P[k+p]=(x+y)%MOD; | ||
| + | if(opt==-1) P[k]=1ll*P[k]*inv2%MOD,P[k+p]=1ll*P[k+p]*inv2%MOD; | ||
| + | } | ||
| + | } | ||
| + | } | ||
| } | } | ||
2020-2021/teams/legal_string/王智彪/fwt.1628831226.txt.gz · 最后更改: 2021/08/13 13:07 由 王智彪
