FWT 整理

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

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

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

或卷积

或的 FWT 是：

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

也就是 每个数的子集和。

或卷积满足

$$F 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 是：

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

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

与卷积是：

$$F 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 是最离谱的，

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

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

关于 xor 卷积的递推：

$$F 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 的逆卷积，推出来是

$$\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;
				}
	}