Loading... 因为每次做异或的题都感觉不好下手, 然而异或是一种性质非常多的奇妙运算.所以写一篇总结 ## 异或和数据结构 口胡一下子,可以套线性基,01trie ## 异或的性质 异或可以看做是一种不进位的加法,或者模 $2$ 意义下的加法。有这样一些性质(统一用$\oplus$符号表示异或运算) ### 归零律 $$ a \oplus a = 0 $$ ### 恒等律 $$ a \oplus 0 = a $$ ### 交换律 $$ a \oplus b = b \oplus a $$ **重要推论: 当** $a \oplus b = c$ **时,** $a \oplus c = b$ , $b \oplus c = a$ **同样成立** ### 自反性 $$ a \oplus b \oplus a = b $$ ## 前缀异或 其实我也不知道这个叫前缀异或还是异或差分,反正讲的应该是一个东西. 基本上就是记一个 $sum$ 数组,其 $sum_1 = a_1$, $sum_i = sum_{i-1} \oplus a_i$ 那么这个玩意儿有什么用呢 $$ a_i \oplus a_{i+1} \oplus a_j = sum_j \oplus sum_{i -1} $$ 好了没了 最后修改:2021 年 09 月 04 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 如果觉得我的文章对你有用,请随意赞赏