FWT 快速瓦尔时变换
yyb的总结还是很到位！
or和and运算非常好理解，可以用子集反演直观的证明。当然也可以用yyb博客中的归纳法证明。
不过抑或是怎么构造的，还不知道。只知道证明是对的。
对于IFWT，直接考虑怎么把多的贡献减掉，或者解个方程变换回原来的值
对于and和or的IFWT，还可以从子集反演的角度想： 
文章图片
因为FWT不是多项式卷积的形式，所以它的点值具有特殊意义，总之要相乘后恰好等于卷积后的系数。这可以看成广义卷积的原理： F W T ( A ) ? F W T ( B ) = F W T ( ( A o p t B ) = C ) FWT(A) * FWT(B) = FWT((A opt B) = C) FWT(A)?FWT(B)=FWT((AoptB)=C) 我们可以通过特定运算构造C。
还有mod 10意义下的FWT 【知识点总结|【学习小结】FWT 快速瓦尔时变换和子集反演】这道题仍然留坑
子集反演的技巧和例题 to be continue
推荐阅读
- AIoT(人工智能+物联网)|程序员的数学【线性代数基础】
- topcoder|Topcoder SRM 661 Div1 Easy: MissingLCM
- HDU 5184 Brackets (卡特兰数)
- 高斯消元
- 水题纪念|【51nod - 1098】 最小方差（基础数学，公式化简，前缀和，积的前缀和）
- 扩展欧几里德算法（gcd扩展使用）
- 数学|CF 514D.Nature Reserve 几何,二分,交集
- codeforces|Codeforces Round #665 (Div. 2) C. Mere Array(数学)
- codeforces|Codeforces Round #665 (Div. 2) A. Distance and Axis(思维，数学)
- 数论|Codeforces Global Round 10 B. Omkar and Infinity Clock(数学)