关于 FWT 的一些理解

本文作者为 JustinRochester ，转载本文请先与作者本人联系，并注明本文原作者。凡未经允许，私自转载且不注明作者的人，均构成侵权

规定 (otimes) 为任一位运算，给定数组 (a_n,b_n) ，求数组 (displaystyle c_n=sum_{iotimes j=n}a_ib_j)

我们假设将数组 (a_n,b_n,c_n) 分别看成一个向量，并对该三个向量进行线性变换。

(c_n) 的线性变换可逆

设线性变换分别为 (T_A,T_B,T_C) ，且线性变换后，新数组 (a'_n,b'_n,c'_n) 满足 (c'_n=a'_ncdot b'_n)

则 (vec {i'}=T_icdot vec i)

故 (vec c=T_C^{-1}vec {c'}=T_C^{-1}(vec {a'}cdot vec {b'})=T_C^{-1}[(T_Avec a)cdot (T_Bvec b)])

这里的 (vec acdot vec b) 代表对应位相乘

将满足的等式代入线性变换得 (displaystyle sum_i T_{C(n,i)}c_i=c'_n=a'_ncdot b'_n=sum_p T_{A(n,p)}a_psum_q T_{B(n,q)}b_q)

代入 (displaystyle c_n=sum_{iotimes j=n}a_ib_j) 得

(displaystyle sum_i T_{C(n,i)}sum_{potimes q}a_pb_q=sum_p sum_q T_{B(n,q)} T_{A(n,p)}a_pb_q)

(displaystyle sum_psum_q T_{C(n,potimes q)}a_pb_q=sum_p sum_q T_{B(n,q)} T_{A(n,p)}a_pb_q)

约除相同项，我们得到 (displaystyle T_{C(n,potimes q)}=T_{B(n,q)} T_{A(n,p)})

由于位运算的可按位拆解性，我们得到，对于每一位 (b) ，都有 (displaystyle T_C(n_b,p_botimes_b q_b)=T_B(n_b,q_b) T_A(n_b,p_b))

又由于二进制每位的取值只有 (0) 或 (1) ，我们对于 (T_i) 只需要构造矩阵 ( left( egin{matrix} T_i(0, 0)&T_i(0, 1) \ T_i(1, 0)&T_i(1, 1) end{matrix} ight) ) ，并且满足上述条件即可

当然 (T_C) 必须可逆，即 (T_C) 满秩，行列式 (T_C(0, 0)T_C(1, 1)-T_C(0, 1)T_C(1, 0) eq 0)

当对矩阵中仅有第 (i) 位不同的两个值 (v_l,v_r(v_l<v_r)) 进行计算时，有：

(left( egin{matrix} v'_l \ v'_r end{matrix} ight)= left( egin{matrix} T_i(0, 0)&T_i(0, 1) \ T_i(1, 0)&T_i(1, 1) end{matrix} ight)cdot left( egin{matrix} v_l \ v_r end{matrix} ight)= left( egin{matrix} T_i(0, 0)v_l+T_i(0, 1)v_r \ T_i(1, 0)v_l+T_i(1, 1)v_r end{matrix} ight))

当 (otimes) 为按位或时：构造矩阵 (T_A=T_B=T_C= left( egin{matrix} 1&0 \ 1&1 end{matrix} ight) )

则 (q_b=p_b=0) 时 (T_C(n_b, q_bvee p_b)=T_C(n_b, 0)=1=1cdot 1=T_A(n_b,0)cdot T_B(n_b, 0)=T_A(n_b,q_b)cdot T_B(n_b,p_b))

否则 (T_C(n_b,q_bvee p_b)=T_C(n_b, 1)=n_b=T_A(n_b,q_b)cdot T_A(n_b,p_b))

由于 ( ext{det }T_C=0-1 eq 0) ，故存在 (T_C^{-1}= left( egin{matrix} 1&0 \ -1&1 end{matrix} ight))

所以进行 FWT 时，代码如下：

for(int b=0;1<<b<len;++b) for(int i=0;i<len;++i) if (~i>>b&1) {
	int j=i^(1<<b);
        a[j]=add(a[j],a[i]);
}

而进行逆变换 UFWT 时，代码如下：

for(int b=0;1<<b<len;++b) for(int i=0;i<len;++i) if (~i>>b&1) {
	int j=i^(1<<b);
        a[j]=dis(a[j],a[i]);
}

当 (otimes) 为按位与时：构造矩阵 (T_A=T_B=T_C= left( egin{matrix} 1&1 \ 0&1 end{matrix} ight) )

当 (otimes) 为按位异或时：构造矩阵 (T_A=T_B=T_C= left( egin{matrix} 1&1 \ 1&-1 end{matrix} ight) )

当 (otimes) 为按位同或时：构造矩阵 (T_A=T_B=T_C= left( egin{matrix} -1&1 \ 1&1 end{matrix} ight) )

当然，我们知道，单个位的位运算是一个 ({0, 1} imes{0, 1} o{0, 1}) 的二元函数 (f(x,y))

因此，函数的个数应为 (|{0, 1}^{{0, 1} imes{0, 1}}|=|{0, 1}|^{|{0, 1} imes{0, 1}|}=2^{2 imes 2}=16) 种

因此，我们如果能求出这 (16) 种的位运算计算方法，理论上能求解所有的奇葩位运算

(S) (1otimes 1) (1otimes 0) (0otimes 1) (0otimes 0) (T_A) (T_B) (T_C) (T_C^{-1})
(0) (0) (0) (0) (0) (left(egin{matrix}1&1 \ 0&0end{matrix} ight)) (left(egin{matrix}1&1 \ 0&0end{matrix} ight)) (left(egin{matrix}1&0 \ 0&1end{matrix} ight)) (left(egin{matrix}1&0 \ 0&1end{matrix} ight))
(1) (0) (0) (0) (1) (left(egin{matrix}1&1 \ 0&1end{matrix} ight)) (left(egin{matrix}1&1 \ 0&1end{matrix} ight)) (left(egin{matrix}1&1 \ 0&1end{matrix} ight)) (left(egin{matrix}1&-1 \ 0&1end{matrix} ight))
(2) (0) (0) (1) (0) (left(egin{matrix}1&1 \ 0&1end{matrix} ight)) (left(egin{matrix}1&1 \ 1&0end{matrix} ight)) (left(egin{matrix}1&1 \ 0&1end{matrix} ight)) (left(egin{matrix}1&-1 \ 0&1end{matrix} ight))
(3) (0) (0) (1) (1) (left(egin{matrix}1&0 \ 0&1end{matrix} ight)) (left(egin{matrix}1&1 \ 1&1end{matrix} ight)) (left(egin{matrix}1&0 \ 0&1end{matrix} ight)) (left(egin{matrix}1&0 \ 0&1end{matrix} ight))
(4) (0) (1) (0) (0) (left(egin{matrix}1&1 \ 1&0end{matrix} ight)) (left(egin{matrix}1&1 \ 0&1end{matrix} ight)) (left(egin{matrix}1&1 \ 0&1end{matrix} ight)) (left(egin{matrix}1&-1 \ 0&1end{matrix} ight))
(5) (0) (1) (0) (1) (left(egin{matrix}1&1 \ 1&1end{matrix} ight)) (left(egin{matrix}1&0 \ 0&1end{matrix} ight)) (left(egin{matrix}1&0 \ 0&1end{matrix} ight)) (left(egin{matrix}1&0 \ 0&1end{matrix} ight))
(6) (0) (1) (1) (0) (left(egin{matrix}1&1 \ 1&-1end{matrix} ight)) (left(egin{matrix}1&1 \ 1&-1end{matrix} ight)) (left(egin{matrix}1&1 \ 1&-1end{matrix} ight)) (left(egin{matrix}{1over 2}&{1over 2} \ {1over 2}&-{1over 2}end{matrix} ight))
(7) (0) (1) (1) (1) (left(egin{matrix}1&0 \ 1&1end{matrix} ight)) (left(egin{matrix}1&0 \ 1&1end{matrix} ight)) (left(egin{matrix}1&0 \ 1&1end{matrix} ight)) (left(egin{matrix}1&0 \ -1&1end{matrix} ight))
(8) (1) (0) (0) (0) (left(egin{matrix}1&1 \ 1&0end{matrix} ight)) (left(egin{matrix}1&1 \ 1&0end{matrix} ight)) (left(egin{matrix}1&1 \ 0&1end{matrix} ight)) (left(egin{matrix}1&-1 \ 0&1end{matrix} ight))
(9) (1) (0) (0) (1) (left(egin{matrix}1&-1 \ 1&1end{matrix} ight)) (left(egin{matrix}1&-1 \ 1&1end{matrix} ight)) (left(egin{matrix}-1&1 \ 1&1end{matrix} ight)) (left(egin{matrix}-{1over 2}&{1over 2} \ {1over 2}&{1over 2}end{matrix} ight))
(10) (1) (0) (1) (0) (left(egin{matrix}1&1 \ 1&1end{matrix} ight)) (left(egin{matrix}0&1 \ 1&0end{matrix} ight)) (left(egin{matrix}1&0 \ 0&1end{matrix} ight)) (left(egin{matrix}1&0 \ 0&1end{matrix} ight))
(11) (1) (0) (1) (1) (left(egin{matrix}1&0 \ 1&1end{matrix} ight)) (left(egin{matrix}0&1 \ 1&1end{matrix} ight)) (left(egin{matrix}1&0 \ 1&1end{matrix} ight)) (left(egin{matrix}1&0 \ -1&1end{matrix} ight))
(12) (1) (1) (0) (0) (left(egin{matrix}0&1 \ 1&0end{matrix} ight)) (left(egin{matrix}1&1 \ 1&1end{matrix} ight)) (left(egin{matrix}1&0 \ 0&1end{matrix} ight)) (left(egin{matrix}1&0 \ 0&1end{matrix} ight))
(13) (1) (1) (0) (1) (left(egin{matrix}0&1 \ 1&1end{matrix} ight)) (left(egin{matrix}1&0 \ 1&1end{matrix} ight)) (left(egin{matrix}1&0 \ 1&1end{matrix} ight)) (left(egin{matrix}1&0 \ -1&1end{matrix} ight))
(14) (1) (1) (1) (0) (left(egin{matrix}0&1 \ 1&1end{matrix} ight)) (left(egin{matrix}0&1 \ 1&1end{matrix} ight)) (left(egin{matrix}1&0 \ 1&1end{matrix} ight)) (left(egin{matrix}1&0 \ -1&1end{matrix} ight))
(15) (1) (1) (1) (1) (left(egin{matrix}0&0 \ 1&1end{matrix} ight)) (left(egin{matrix}0&0 \ 1&1end{matrix} ight)) (left(egin{matrix}1&0 \ 0&1end{matrix} ight)) (left(egin{matrix}1&0 \ 0&1end{matrix} ight))

采用卡诺图化简法得到：

(T_A=left( egin{matrix} overline{S_3wedge S_2}&(overline{S_1wedge S_0})cdot (-1)^{[S=9]} \ S_3vee S_2&(S_1vee S_0)cdot (-1)^{[S=6]} end{matrix} ight))

(T_B=left( egin{matrix} overline{S_3wedge S_1}&(overline{S_2wedge S_0})cdot (-1)^{[S=9]} \ S_3vee S_1&(S_2vee S_0)cdot (-1)^{[S=6]} end{matrix} ight))

(T_C=left( egin{matrix} (-1)^{[S=9]}&(S_2vee S_1)oplus(S_3vee S_0) \ (S_2wedge S_1)oplus(S_3wedge S_0)&(-1)^{[S=6]} end{matrix} ight))

(displaystyle T_C^{-1}={1over ext{det }T_C} left( egin{matrix} T_{1, 1}&-T_{0, 1} \ -T_{1, 0}&T_{0, 0} end{matrix} ight) =(-{1over 2})^{[S=6vee S=9]}left( egin{matrix} (-1)^{[S=6]}&-(S_2vee S_1)oplus(S_3vee S_0) \ -(S_2wedge S_1)oplus(S_3wedge S_0)&(-1)^{[S=9]} end{matrix} ight))

inline void updl(ll &a0,ll &a1,int S){
	bool S0=(S&1),S1=(S>>1&1),S2=(S>>2&1),S3=(S>>3&1);
	__int128 A0=a0,A1=a1;
	a0=(S3&S2?0:A0) + (S1&S0?0:A1)*(S==9?-1:1);
	a1=(S3|S2?A0:0) + (S1|S0?A1:0)*(S==6?-1:1);
}
inline void updr(ll &a0,ll &a1,int S){
	bool S0=(S&1),S1=(S>>1&1),S2=(S>>2&1),S3=(S>>3&1);
	__int128 A0=a0,A1=a1;
	a0=(S3&S1?0:A0) + (S2&S0?0:A1)*(S==9?-1:1);
	a1=(S3|S1?A0:0) + (S2|S0?A1:0)*(S==6?-1:1);
}
inline void updi(ll &a0,ll &a1,int S){
	bool S0=(S&1),S1=(S>>1&1),S2=(S>>2&1),S3=(S>>3&1);
	__int128 A0=a0,A1=a1;
	a0=( (S==6?-A0:A0)-( ((S2|S1)^(S3|S0))?A1:0 ) )*(S==6|S==9?-1:1)>>(S==6|S==9);
	a1=( ( ((S2&S1)^(S3&S0))?-A0:0 )+(S==9?-A1:A1) )*(S==6|S==9?-1:1)>>(S==6|S==9);
}
inline void FWT(ll *a,int n,void (*upd)(ll&,ll&,int) ){
	for(int i=1;i<n;i<<=1) for(int S=0;S<n;++S)
		if( (~S)&i )
			upd(a[S],a[S|i],Sta[__builtin_ctz(i)]);
}
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/JustinRochester/p/14589653.html