以前写容斥原理时,用的都是dfs~

今天突然想到...格雷碼,每次只改变一位,貌似可以用来写容斥原理;

然后就写了一个

const int BT[]={0,1,28,2,29,14,24,3,30,22,20,15,25,17,4,8,31,27,13,23,21,19,16,7,26,12,18,6,11,5,10,9};
#define BIT4CHG(i) BT[(unsigned int)((((i)+1)&~(i))*0x077CB531U)>>27]

其中的BIT4CHG,就是告诉你第i个格雷碼变成第i+1个时(i从0开始算),改变的是第几位~之所以可读性这么差是因为使用了这里的技巧.

这就避免了dfs递归了......

其实,这个效率确实提高不了多少~而且写起来没那么好看~