状态压缩Abstract信息学发展势头迅猛，信息学奥赛的题目来源遍及各行各业，经常有一些在实际应用中很有价值的问题被引入信息学并得到有效解决。

然而有一些问题却被认为很可能不存在有效的(多项式级的)算法，本文以对几个例题的剖析，简述状态压缩思想及其应用。

Keywords状态压缩、集合、Hash、NPCContentIntroducti o n作为OIers，我们不同程度地知道各式各样的算法。

这些算法有的以O(logn)的复杂度运行，如二分查找、欧几里德GCD算法(连续两次迭代后的余数至多为原数的一半)、平衡树，有的以O(n)运行，例如二级索引、块状链表，再往上有O(n)、O(n p log q n)……大部分问题的算法都有一个多项式级别的时间复杂度上界1，我们一般称这类问题2为P类(deterministic Polynomial-time)问题，例如在有向图中求最短路径。

然而存在几类问题，至今仍未被很好地解决，人们怀疑他们根本没有多项式时间复杂度的算法，它们是NPC(NP-Complete)和NPH(NP-Hard)类，例如问一个图是否存在哈密顿圈(NPC)、问一个图是否不存在哈密顿圈(NPH)、求一个完全图中最短的哈密顿圈(即经典的Traveling Salesman Problem货郎担问题，NPH)、在有向图中求最长(简单)路径(NPH)，对这些问题尚不知有多项式时间的算法存在。

P和NPC都是NP(Non-deterministic Polynomial-time)的子集，NPC则代表了NP类中最难的一类问题，所有的NP类问题都可以在多项式时间内归约到NPC问题中去。

NPH包含了NPC和其他一些不属于NP(也更难)的问题(即NPC是NP与NPH的交集)，NPC问题的最优化版本一般是NPH的，例如问一个图是否存在哈密顿圈是NPC的，但求最短的哈密顿圈则是NPH的，原因在于我们可以在多项式时间内验证一个回路是否真的是哈密顿回路，却无法在多项式时间内验证其是否是最短的，NP类要求能在多项式时间内验证问题的一个解是否真的是一个解，所以最优化TSP问题不是NP的，而是NPH的。

存在判定性TSP问题，它要求判定给定的完全图是否存在权和小于某常数v的哈密顿圈，这个问题的解显然可以在多项式时间内验证，1请注意，大O符号表示上界，即O(n)的算法可以被认为是O(n2)的，O(n p log q n)可以被认为是O(n p+1)的。

2在更正式的定义中，下面提到的概念都只对判定性问题或问题的判定版本才存在。

Levin给出了一个适用因此它是NP的，更精确地说是NPC的。

1如上所述，对于NPC和NPH问题，至今尚未找到多项式时间复杂度的算法。

然而它们的应用又是如此的广泛，我们不得不努力寻找好的解决方案。

毫无疑问，对于这些问题，使用暴力的搜索是可以得到正确的答案的，但在信息学竞赛那有限的时间内，很难写出速度可以忍受的暴力搜索。

例如对于TSP问题，暴力搜索的复杂度是O(n!)，如此高的复杂度使得它对于高于10的数据规模就无能为力了。

那么，有没有一种算法，它可以在很短的时间内实现，而其最坏情况下的表现比搜索好呢？答案是肯定的——状态压缩(States Compression，SC)。

作为对下文的准备，这里先为使用Pascal的OIers简要介绍一下C/C++样式的位运算(bitwise operation)。

以上各运算符的优先级从高到低依次为：二、特殊应用a)and：i.用以取出一个数的某些二进制位ii.取出一个数的最后一个1(lowbit)2：x&-xb)or ：用以将一个数的某些位设为1c)not：用以间接构造一些数：~0=4294967295=232-1d)xor：i.不使用中间变量交换两个数：a=a^b;b=a^b;a=a^b;ii.将一个数的某些位取反有了这些基础，就可以开始了。

1不应该混淆P、NP、NPC、NPH的概念。

这里只是粗略介绍，详见关于算法分析的书籍，这会使新手读者的理论水平上一个台阶。

弄不明白也没关系，基本不影响对本文其他部分的理解^_^2具有同样作用的还有(x-1)&x^x,这个的道理更容易理解。

lowbit在树状数组(某种数据结构)中可以用到，这里不再单独介绍，感兴趣的可以参阅各牛的论文，或者加我QQ。

建议掌握，否则可能会看不懂我Getting Started我们暂时避开状态压缩的定义，先来看一个小小的例题。

【引例】1在n*n(n≤20)的方格棋盘上放置n个车(可以攻击所在行、列)，求使它们不能互相攻击的方案总数。

【分析】这个题目之所以是作为引例而不是例题，是因为它实在是个非常简单的组合学问题：我们一行一行放置，则第一行有n种选择，第二行n-1，……，最后一行只有1种选择，根据乘法原理，答案就是n!。

这里既然以它作为状态压缩的引例，当然不会是为了介绍组合数学。

我们下面来看另外一种解法：状态压缩递推(States Compressing Recursion,SCR)。

我们仍然一行一行放置。

取棋子的放置情况作为状态，某一列如果已经放置棋子则为1，否则为0。

这样，一个状态就可以用一个最多20位的二进制数2表示。

例如n=5,第1、3、4列已经放置，则这个状态可以表示为01101(从右到左)。

设f[s]为达到状态s的方案数，则可以尝试建立f的递推关系。

考虑n=5,s=01101。

这个状态是怎么得到的呢？因为我们是一行一行放置的，所以当达到s时已经放到了第三行。

又因为一行能且仅能放置一个车，所以我们知道状态s一定来自：①前两行在第3、4列放置了棋子(不考虑顺序，下同)，第三行在第1列放置；②前两行在第1、4列放置了棋子，第三行在第3列放置；③前两行在第1、3列放置了棋子，第三行在第4列放置。

这三种情况互不相交，且只可能有这三种情况。

根据加法原理，f[s]应该等于这三种情况的和。

写成递推式就是：f[01101]=f[01100]+f[01001]+f[00101]根据上面的讨论思路推广之，得到引例的解决办法：f[0]=1f[s]=∑f[s^2i]其中s∈[0…01,1…11]，s的右起第i+1位为1。

3反思这个算法，其正确性毋庸置疑(可以和n!对比验证)。

但是算法的时间复杂度为O(n2n)，空间复杂度O(2n)，是个指数级的算法，比循环计算n!差了好多，它有什么优势？较大的推广空间。

4Sample Problems【例1】5在n*n(n≤20)的方格棋盘上放置n个车，某些格子不能放，求使它们不能互1本文所有例题的C++代码均可以在附件中找到。

2方便、整齐起见，本文中不在数的后面标明进制。

3考虑上节介绍的位运算的特殊应用，可以更精巧地实现。

4还有一个很…的用处，即对新手说：“来看看我这个计算n!的程序，连这都看不懂就别OI了~”相攻击的方案总数。

【分析】对于这个题目，如果组合数学学得不够扎实，你是否还能一眼看出解法？应该很难。

对于这个题目，确实存在数学方法(容斥原理)，但因为和引例同样的理由，这里不再赘述。

联系引例的思路，发现我们并不需要对算法进行太大的改变。

引例的算法是在枚举当前行(即s 中1的个数，设为r)的放置位置(即枚举每个1)，而对于例1，第r 行可能存在无法放置的格子，怎么解决这个问题呢？枚举1的时候判断一下嘛！事实的确是这样，枚举1的时候判断一下是否是不允许放置的格子即可。

但是对于n=20，O(n2n )的复杂度已经不允许我们再进行多余的判断。

所以实现这个算法时应该应用一些技巧。

对于第r 行，我们用a[r]表示不允许放置的情况，如果某一位不允许放置则为1，否则为0，这可以在读入数据阶段完成。

运算时，对于状态s ，用tmps=s^a[r]来代替s 进行枚举，即不枚举s 中的1转而枚举tmps 中的1。

因为tmps 保证了无法放置的位为0，这样就可以不用多余的判断来实现算法，代码中只增加了计算a 数组和r 的部分，而时间复杂度没有太大变化。

这样，我们直接套用引例的算法就使得看上去更难的例1得到了解决。

你可能会说，这题用容斥原理更快。

没错，的确是这样。

但是，容斥原理在这题上只有当棋盘为正方形、放入的棋子个数为n 、且棋盘上禁止放置的格子较少时才有简单的形式和较快的速度。

如果再对例1进行推广，要在m*n 的棋盘上放置k 个车，那么容斥原理是无能为力的，而SCR 算法只要进行很少的改变就可以解决问题1。

这也体现出了引例中给出的算法具有很大的扩展潜力。

棋盘模型是状态压缩最好的展示舞台之一。

下面再看几个和棋盘有关的题目。

【例2】2给出一个n*m 的棋盘(n 、m ≤80,n*m ≤80)，要在棋盘上放k(k ≤20)个棋子，使得任意两个棋子不相邻。

每次试验随机分配一种方案，求第一次出现合法方案时试验的期望次数，答案用既约分数表示。

【分析】显然，本题中的期望次数应该为出现合法方案的概率的倒数，则问题转化为求出现合法方案的概率。

而概率=方案总数合法方案数，方案总数显然为C(n*m,k)，则问题转化为求合法方案数。

整理一下，现在的问题是：在n*m 的棋盘上放k 个棋子，求使得任意两个棋子不相邻的放置方案数。

这个题目的状态压缩模型是比较隐蔽的。

观察题目给出的规模，n 、m ≤80，这个规模要想用SC 是困难的，若同样用上例的状态表示方法(放则为1，不放为0)，280无论在时间还是在空间上都无法承受。

然而我们还看到n*m ≤80，这种给出数据规模的方法是不多见的，有什么玄机呢？能把状态数控制在可以承受的1如果这样改编，则状态的维数要增加，如有疑问可以参考下面的几个例子，这里不再赘述。

范围吗？稍微一思考，我们可以发现：9*9=81>80，即如果n,m都大于等于9，将不再满足n*m≤80这一条件。

所以，我们有n或m小于等于8，而28是可以承受的。

我们假设m≤n(否则交换，由对称性知结果不变)n是行数m是列数，则每行的状态可以用m位的二进制数表示。

但是本题和例1又有不同：例1每行每列都只能放置一个棋子，而本题却只限制每行每列的棋子不相邻。

但是，上例中枚举当前行的放置方案的做法依然可行。

我们用数组s[1..num]1保存一行中所有的num个放置方案，则s数组可以在预处理过程中用DFS求出，同时用c[i]保存第i个状态中1的个数以避免重复计算。

开始设计状态。

如注释一所说，维数需要增加，原因在于并不是每一行只放一个棋子，也不是每一行都要求有棋子，原先的表示方法已经无法完整表达一个状态。

我们用f[i][j][k]表示第i行的状态为s[j]且前i行已经放置了k个棋子2的方案数。

沿用枚举当前行方案的做法，只要当前行的方案和上一行的方案不冲突即可，“微观”地讲，即s[snum[i]]和s[snum[i-1]]没有同为1的位，其中snum[x]表示第x行的状态的编号。