异或前后 1 的个数的奇偶性
异或前后 1 的个数的奇偶性
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132915268
一个常见套路
考虑异或操作，其前后1的个数奇偶性不会发生改变
因为每位要么没1，要么保留1个1，要么同时消掉2个1
这个结论可以方便我们构造fwt的转移系数
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-10-13
树上启发式合并：GYM102832F
树上启发式合并：GYM102832F 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133802611 https://vjudge.net/contest/587311#problem/C 最近没打这个套路，场上忘了 发现和一堆lca什么的有关，然后又是lca下不同的儿子，考虑树上启发式合并。 对于 i⊕ji\oplus ji⊕j ，我们可以拆位枚举 然后常数大会被卡常。但树上启发式合并很多的dfs可以优化成遍历dfs序上一段连续的区间。 123456...
2023-09-07
异或和大小比较类问题——抓住最高位：CF1863F
异或和大小比较类问题——抓住最高位：CF1863F 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132629186 https://codeforces.com/contest/1863/problem/F 因为有等于，所以考虑异或和为0的合法区间，它可以随意切 现在考虑切开后左边大于右边，可以发现左右边最高位可以互相抵消，似乎不太可做？ 此时可以换个考虑，考虑大区间的异或和的最高位，这一位在左右两个区间 恰好 有一位为1，而为1的那个区间就是...