FWT 整理

FWT 整理

以前我记得是正式写过 FWT 的总结的但是貌似没找到

作为一个背板选手详细证明被咕咕咕了,可以见 LSJ的blog

注意几种卷积都满足可加性。

或卷积

或的 FWT 是:

FWTor(A)[i]=jiA[j]FWT_{or}(A)[i] = \sum_{j\subseteq i} A[j]

也就是 每个数的子集和。

或卷积满足

FWT(A)={(FWT(A0),FWT(A0)+FWT(A1))n>1An=0F W T(A)=\left\{\begin{array}{ll}\left(F W T\left(A_{0}\right), F W T\left(A_{0}\right)+F W T\left(A_{1}\right)\right) & n>1 \\A & n=0\end{array}\right.

也就是说后一半加上前一半,代码长这样:

inline void FWTor(ll a[], int len) {
		for (int mid = 2; mid <= len; mid <<= 1) 
			for (int i = 0; i < len; i += mid)
				for (int j = i; j < i + (mid >> 1); j++) 
					( a[j + (mid >> 1)] += a[j] ) %= P;
	}

与卷积

与的 FWT 是:

FWTand(A)[i]=ijA[j]FWT_{and}(A)[i] = \sum_{i\subseteq j} A[j]

也就是说是 每个数的超集的和。

与卷积是:

FWT(A)={(FWT(A0)+FWT(A1),FWT(A1))n>1An=0F W T(A)=\left\{\begin{array}{ll}\left(F W T\left(A_{0}\right)+F W T\left(A_{1}\right), F W T\left(A_{1}\right)\right) & n>1 \\A & n=0\end{array}\right.

也就是前一半分别加上后一半,代码长这样:

inline void FWTand(ll a[], int len) {
		for (int mid = 2; mid <= len; mid <<= 1) 
			for (int i = 0; i < len; i += mid)
				for (int j = i; j < i + (mid >> 1); j++) 
					( a[j] += a[j + (mid >> 1)] ) %= P;
	}

与卷积和或卷积的逆运算

最后推出的结论是,它们正好是把原来的卷积的 加减号 取反。详细证明不想写了。。

inline void IFWTor(ll a[], int len) {
		for (int mid = 2; mid <= len; mid <<= 1) 
			for (int i = 0; i < len; i += mid)
				for (int j = i; j < i + (mid >> 1); j++) 
					( a[j + (mid >> 1)] += P - a[j] ) % P;
	}
inline void IFWTand(ll a[], int len) {
		for (int mid = 2; mid <= len; mid <<= 1) 
			for (int i = 0; i < len; i += mid)
				for (int j = i; j < i + (mid >> 1); j++) 
					( a[j] += P - a[j + (mid >> 1)] ) % P;
	}

异或卷积

这个的 FWT 是最离谱的,

FWTxor(A)[i]=jAj(1)popcount(j&i)FWT_{xor}(A)[i] = \sum_{j}A_j(-1)^{popcount(j\&i)}

也就是说每个数字的系数是它和 ii 的共同的 1 的个数的奇偶行

关于 xor 卷积的递推:

FWT(A)={(FWT(A0)+FWT(A1),FWT(A0)FWT(A1))n>0An=0F W T(A)=\left\{\begin{array}{ll}\left(F W T\left(A_{0}\right)+F W T\left(A_{1}\right), F W T\left(A_{0}\right)-F W T\left(A_{1}\right)\right) & n>0 \\A & n=0\end{array}\right.

也就是,前一半变成前面和后面的和,后一半变成前面和后面的差。代码长这样:

inline void FWTxor(ll a[], int len) {
		for (int mid = 2; mid <= len; mid <<= 1) 
			for (int i = 0; i < len; i += mid)
				for (int j = i; j < i + (mid >> 1); j++) {
					ll x = a[j], y = a[j + (mid >> 1)];
					a[j] = ( x + y ) % P, a[j + (mid >> 1)] = ( x - y + P ) % P;
				}
	}

关于 xor 的逆卷积,推出来是

IFWT(A)={(IFWT(A0+A1)2,IFWT(A0A1)2)n>1An=0\operatorname{IFWT}(A)=\left\{\begin{array}{ll}\left(\frac{\operatorname{IFWT}\left(A_{0}+A_{1}\right)}{2}, \frac{\operatorname{IFWT}\left(A_{0}-A_{1}\right)}{2}\right) & n>1 \\A & n=0\end{array}\right.

就相当于前一半变成相加除以二,后一半变成相减除以二。

inline void IFWTxor(ll a[], int len) {
		for (int mid = 2; mid <= len; mid <<= 1) 
			for (int i = 0; i < len; i += mid)
				for (int j = i; j < i + (mid >> 1); j++) {
					ll x = a[j], y = a[j + (mid >> 1)];
					// a[j] = (x + y) >> 1, a[j + (mid >> 1)] = (x - y) >> 1;
          a[j] = 1ll * ( x + y ) * inv2 % P , a[j + (mid >> 1)] = 1ll * (x - y) * inv2 % P;
				}
	}
\