1. 数对子
首先发现两个数异或起来有奇数个1 的充要条件就是一个数有奇数个1，另一个有偶数个1
（这个性质我竟然没发现。。。）
然后就转化为求一堆区间的并中有多少个数二进制有奇数个1，多少个数二进制有偶数个1
先把区间离散化成$O(n)$个小区间 把每个区间变成一些小区间
然后只要能求一个区间里有多少个二进制有奇数个1即可 这样是$O(n^2)$
有两种方法：
1、数位dp
2、考虑区间$[l,r]$ 我们只要计算$[1,l-1]$的值和$[1,r]$的值就可以了
发现(0,1),(2,3),(4,5)... 每一对数都是最后一位一个是0，一个是1
然后考虑区间$[1,l]$ 如果l是奇数 那么一半对一半 否则单独判断l就好了
2.逆序对
一直在想偶数往奇数里插的做法
没有想过奇数往偶数插
结论：把每个奇数单独考虑 这样做出来的解一定可行
3.盖房子
①有k个位置不能放（k≤8）（容斥，$2^k$)
②每行每列至少一个
③正负对角线至少一个（容斥，$2^2$)
④正好放n个
现在变成什么问题：
一个格子图，有一些格子放了东西，一些格子不能放东西，某些对角线不能放东西
先把对角线去掉
然后另一条对角线（如果还有）就会变得比较扭曲
然后对角线就解决了
原文：https://www.cnblogs.com/wawawa8/p/9419066.html