模板及讲解
状态压缩动态规划就是用于某种时候DP的状态难以表示时，使用二进制进行存储状态的一种动态规划。通常会用位运算进行操作：
位运算
1、对$x$取反：~x
2、$x+1(x为偶数)$：x|1
3、$2^x$：1<<x
4、$2^{-x}$：1>>x
5、$x的对应值$(例如$0$对$1$，$2$对$3$，$8$对$9$)：x^1
6、构造0~n-1位二进制数全部为1：(1<<n)-1
7、构造形如10,100,100000即[0, k-1]全部为0，[k,k]为1，这样的二进制数：1<<(k-1)
状压DP常用
欲想用状压dp，先在dp方程中加上一维状态S再进行思考有哪些需要知道。
有一些状压 (DP) 可以根据最高位来转移，即低位数+最高位=高位数
1、将a的第k位修改为1：a |= 1<<k;
2、将a的第k位修改为0：a &= ~(1<<k);
3、取第k位：a >> k & 1;
4、判定序列里有没有连续出现的1：a&(a>>1)或a&(a<<1)
5、枚举子集：i = (i - 1) & S
6、取最后一个1：i &= (i - 1)
7、x的二进制表达式中最低位的1所对应的值：lowbit(x) = x & (-x)
三(多)进制状压
我们相当于把一个整数当做三进制数来看，也就是说$(25)_{10}={221}_3$，我们就维护这个$221$。
我们开一个数组sjc[状态][位]=位上的值 (0, 1, 2)，用来找一个状态每一个位上是什么
这个数组可以用十进制转三进制的方法求得，具体看代码。
然后注意本题要特判$k=1，k=n$，并且只有一行的情况。
异或性质
1、$a \oplus a=0$
2、$a \oplus b \oplus c=a \oplus (b \oplus c)$ (右结合律)
3、$a \oplus 0 = a $
异或题：(核心：按位贪心)
1、两个之间的异或值：Trie树 (最大异或和，CF 888G，十二省联考异或粽子)
2、多个之间的异或值：线性基 (Bzoj 4568)
