论文阅读状态压缩

电玩女神 2022-04-23 09:12 257阅读 0赞

# **状态压缩** #

## **Abstract** ##

信息学发展势头迅猛，信息学奥赛的题目来源遍及各行各业，经常有一些在实际应用中很有价值的问题被引入信息学并得到有效解决。然而有一些问题却被认为很可能不存在有效的(多项式级的)算法，本文以对几个例题的剖析，简述状态压缩思想及其应用。

## **Keywords** ##

状态压缩、集合、Hash、NPC

## **Content** ##

### **Introduction** ###

作为OIers，我们不同程度地知道各式各样的算法。这些算法有的以O(logn)的复杂度运行，如二分查找、欧几里德GCD算法(连续两次迭代后的余数至多为原数的一半)、平衡树，有的以O()运行，例如二级索引、块状链表，再往上有O(n)、O(nplogqn)……大部分问题的算法都有一个多项式级别的时间复杂度上界，我们一般称这类问题为**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的哈密顿圈，这个问题的解显然可以在多项式时间内验证，因此它是NP的，更精确地说是NPC的。

如上所述，对于NPC和NPH问题，至今尚未找到多项式时间复杂度的算法。然而它们的应用又是如此的广泛，我们不得不努力寻找好的解决方案。毫无疑问，对于这些问题，使用暴力的搜索是可以得到正确的答案的，但在信息学竞赛那有限的时间内，很难写出速度可以忍受的暴力搜索。例如对于TSP问题，暴力搜索的复杂度是O(n!)，如此高的复杂度使得它对于高于10的数据规模就无能为力了。那么，有没有一种算法，它可以在很短的时间内实现，而其最坏情况下的表现比搜索好呢？答案是肯定的——**状态压缩(States Compression，SC)**。

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

*  基本运算符

<table style="margin-left:41.4pt;width:362.7pt;"> 
 <tbody> 
 <tr> 
 <td style="vertical-align:top;width:90.7pt;"> 名称 </td> 
 <td style="vertical-align:top;width:83pt;"> C/C++样式 </td> 
 <td style="vertical-align:top;width:90pt;"> Pascal样式 </td> 
 <td style="vertical-align:top;width:99pt;"> 简记法则 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:90.7pt;"> 按位与 (bitwise AND) </td> 
 <td style="vertical-align:top;width:83pt;"> &amp; </td> 
 <td style="vertical-align:top;width:90pt;"> and </td> 
 <td style="vertical-align:top;width:99pt;"> 全一则一 否则为零 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:90.7pt;"> 按位或 (bitwise OR) </td> 
 <td style="vertical-align:top;width:83pt;"> | </td> 
 <td style="vertical-align:top;width:90pt;"> or </td> 
 <td style="vertical-align:top;width:99pt;"> 有一则一 否则为零 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:90.7pt;"> 按位取反 (bitwise NOT) </td> 
 <td style="vertical-align:top;width:83pt;"> ~ </td> 
 <td style="vertical-align:top;width:90pt;"> not </td> 
 <td style="vertical-align:top;width:99pt;"> 是零则一 是一则零 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:90.7pt;"> 按位异或 (bitwise XOR) </td> 
 <td style="vertical-align:top;width:83pt;"> ^ </td> 
 <td style="vertical-align:top;width:90pt;"> xor </td> 
 <td style="vertical-align:top;width:99pt;"> 不同则一 相同则零 </td> 
 </tr> 
 </tbody> 
</table>

以上各运算符的优先级从高到低依次为：**~,&,^,|**

*  特殊应用
    
    1.  and：
        
        1.  用以取出一个数的某些二进制位
        2.  取出一个数的最后一个1(lowbit) ：x&-x
    2.  or ：用以将一个数的某些位设为1
    3.  not：用以间接构造一些数：~0=4294967295=232-1
    4.  xor：
        
        1.  不使用中间变量交换两个数：a=a^b;b=a^b;a=a^b;
        2.  将一个数的某些位取反

有了这些基础，就可以开始了。

### **Getting Started** ###

我们暂时避开状态压缩的定义，先来看一个小小的例题。

【引例】

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

【分析】

这个题目之所以是作为引例而不是例题，是因为它实在是个非常简单的组合学问题：我们一行一行放置，则第一行有n种选择，第二行n-1，……，最后一行只有1种选择，根据乘法原理，答案就是n!。这里既然以它作为状态压缩的引例，当然不会是为了介绍组合数学。我们下面来看另外一种解法：**状态压缩递推(States Compressing R****ecursion****,SCR)**。

我们仍然一行一行放置。取棋子的放置情况作为状态，某一列如果已经放置棋子则为1，否则为0。这样，一个状态就可以用一个最多20位的二进制数表示。例如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\]=1**

**f\[s\]=∑f\[s****^2****i****\]**

其中s∈\[0…01,1…11\]，s的右起第i+1位为1。

反思这个算法，其正确性毋庸置疑(可以和n!对比验证)。但是算法的时间复杂度为O(n2n)，空间复杂度O(2n)，是个指数级的算法，比循环计算n!差了好多，它有什么优势？较大的推广空间。

### **Sample Problems** ###

【例1】

在n\*n(n≤20)的方格棋盘上放置n个车，某些格子不能放，求使它们不能互相攻击的方案总数。

【分析】

对于这个题目，如果组合数学学得不够扎实，你是否还能一眼看出解法？应该很难。对于这个题目，确实存在数学方法(容斥原理)，但因为和引例同样的理由，这里不再赘述。

联系引例的思路，发现我们并不需要对算法进行太大的改变。引例的算法是在枚举当前行(即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算法只要进行很少的改变就可以解决问题。这也体现出了引例中给出的算法具有很大的扩展潜力。

棋盘模型是状态压缩最好的展示舞台之一。下面再看几个和棋盘有关的题目。

【例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，这种给出数据规模的方法是不多见的，有什么玄机呢？能把状态数控制在可以承受的范围吗？稍微一思考，我们可以发现：9\*9=81>80，即如果n,m都大于等于9，将不再满足n\*m≤80这一条件。所以，我们有n或m小于等于8，而28是可以承受的。我们假设m≤n(否则交换，由对称性知结果不变)n是行数m是列数，则每行的状态可以用m位的二进制数表示。但是本题和例1又有不同：例1每行每列都只能放置一个棋子，而本题却只限制每行每列的棋子不相邻。但是，上例中枚举当前行的放置方案的做法依然可行。我们用数组s\[1..num\]保存一行中所有的num个放置方案，则s数组可以在预处理过程中用DFS求出，同时用c\[i\]保存第i个状态中1的个数以避免重复计算。开始设计状态。如注释一所说，维数需要增加，原因在于并不是每一行只放一个棋子，也不是每一行都要求有棋子，原先的表示方法已经无法完整表达一个状态。我们用f\[i\]\[j\]\[k\]表示第i行的状态为s\[j\]且前i行已经放置了k个棋子的方案数。沿用枚举当前行方案的做法，只要当前行的方案和上一行的方案不冲突即可，“微观”地讲，即s\[snum\[i\]\]和s\[snum\[i-1\]\]没有同为1的位，其中snum\[x\]表示第x行的状态的编号。然而，虽然我们枚举了第i行的放置方案，但却不知道其上一行(i-1)的方案。为了解决这个问题，我们不得不连第i-1的状态一起枚举，则可以写出递推式：

**f\[0\]\[1\]\[0\]=1;**

**f\[i\]\[j\]\[k\]=∑f\[i-1\]\[p\]\[k-c\[j\]\]**

其中s\[1\]=0，即在当前行不放置棋子；j和p是需要枚举的两个状态编号，且要求s\[j\]与s\[p\]不冲突，即s\[j\]&s\[p\]=0。

当然，实现上仍有少许优化空间，例如第i行只和第i-1行有关，可以用滚动数组节省空间。

有了合法方案数，剩下的问题就不是很困难了，需要注意的就只有C(n\*m,k)可能超出64位整数范围的问题，这可以通过边计算边用GCD约分来解决，具体可以参考附件中的代码。这个算法时间复杂度O(n\*pn\*num2)，空间复杂度(滚动数组)O(pn\*num)，对于题目给定的规模是可以很快出解的。

通过上文的例题，读者应该已经对状态压缩有了一些感性的认识。下面这个题目可以作为练习。

【例3】

在n\*n(n≤10)的棋盘上放k个国王(可攻击相邻的8个格子)，求使它们无法互相攻击的方案数。

【分析】

其实有了前面几个例子的分析，这个题目应该是可以独立解决的。不过既然确实有疑问，那我们就来分析一下。

首先，你应该能想到将一行的状态DFS出来(如果不能，请返回重新阅读，谢谢)，仍然设为s\[1..num\],同时仍然设有数组c\[1..num\]记录状态对应的1的个数。和例2相同，仍然以f\[i\]\[j\]\[k\]表示第i行状态为s\[j\]，且前i行已经放置了k个棋子的方案数。递推式仍然可以写作：

**f\[0\]\[1\]\[0\]=1;**

**f\[i\]\[j\]\[k\]=∑f\[i-1\]\[p\]\[k-c\[j\]\]**

其中仍要求s\[j\]和s\[p\]不冲突。

可是问题出来了：这题不但要求不能行、列相邻，甚至不能对角线相邻！s\[j\]、s\[p\]不冲突怎么“微观地”表示呢？其实，稍微思考便可以得出方法：用s\[p\]分别和s\[j\]、s\[j\]\*2、s\[j\]/2进行冲突判断即可，原理很显然。解决掉这唯一的问题，接下来的工作就没有什么难度了。算法复杂度同例2。

下一个例题是状态压缩棋盘模型的经典题目，希望解决这个经典的题目能够增长你的自信。

【例4】

给出一个n\*m(n≤100,m≤10)的棋盘，一些格子不能放置棋子。求最多能在棋盘上放置多少个棋子，使得每一行每一列的任两个棋子间至少有两个空格。

【分析】

显然，你应该已经有DFS搜出一行可能状态的意识了(否则请重新阅读之前的内容3遍，谢谢)，依然设为s\[1..num\],依旧有c\[1..num\]保存s中1的个数，依照例1的预处理搞定不能放置棋子的格子。

问题是，这个题目的状态怎么选？继续像例2、3那样似乎不行，原因在于棋子的攻击范围加大了。但是我们照葫芦画瓢：例2、3的攻击范围只有一格，所以我们的状态中只需要有当前行的状态即可进行递推，而本题攻击范围是两格，因此增加一维来表示上一行的状态。用f\[i\]\[j\]\[k\]表示第i行状态为s\[j\]、第i-1行状态为s\[k\]时前i行至多能放置的棋子数，则状态转移方程很容易写出：

**f\[i\]\[j\]\[k\]=max\{f\[i-1\]\[k\]\[l\]\}****+c\[j\]**

其中要求s\[j\],s\[k\],s\[l\]互不冲突。

因为棋子攻击范围为两格，可以直观地想象到num不会很大。的确，由例2中得到的num的计算式并代入d=2、m=10，得到num=60。显然算法时间复杂度为O(n\*num3)，空间复杂度(滚动数组)O(num2)。此算法还有优化空间。我们分别枚举了三行的状态，还需要对这三个状态进行是否冲突的判断，这势必会重复枚举到一些冲突的状态组合。我们可以在计算出s\[1..num\]后算出哪些状态可以分别作为两行的状态，这样在DP时就不需要进行盲目的枚举。这样修改后的算法理论上比上述算法更优，但因为num本身很小，所以这样修改没有显著地减少运行时间。值得一提的是，本题笔者的算法虽然在理论上并不是最优，但由于位运算的使用，截至2月9日，笔者的程序在PKU OJ上长度最短，速度第二快。

这个题目是国内比赛中较早出现的状态压缩题。它告诉我们状态压缩不仅可以像前几个例题那样求方案数，而且可以求最优方案，即状态压缩思想既可以应用到递推上(**SCR**)，又可以应用到DP上(**SCDP**)，更说明其有广泛的应用空间。

看了这么多棋盘模型应用状态压缩的实例，你可能会有疑问，难道状态压缩只在棋盘上放棋子的题目中有用？不是的。我们暂时转移视线，来看看状态压缩在其他地方的应用——**覆盖模型**。

【例5】

给出n\*m (1≤n、m≤11)的方格棋盘，用1\*2的长方形骨牌不重叠地覆盖这个棋盘，求覆盖满的方案数。

【分析】

这也是个经典的组合数学问题：多米诺骨牌完美覆盖问题(或所谓二聚物问题)。有很多关于这个问题的结论，甚至还有个专门的公式：如果m、n中至少有一个是偶数，则结果=。这个公式形式比较简单，且计算的复杂度是O()的，很高效。但是这个公式内还有三角函数，且中学生几乎不可能理解，所以对我们能力的提高没有任何帮助。用SCR算法能较好地解决这个问题。

显然，如果n、m都是奇数则无解(由棋盘面积的奇偶性知)，否则必然有至少一个解(很容易构造出)，所以假设n、m至少有一个偶数，且m≤n(否则交换)。我们依然像前面的例题一样把每行的放置方案DFS出来，逐行计算。用f\[i\]\[s\]表示把前i-1行覆盖满、第i行覆盖状态为s的覆盖方案数。因为在第i行上放置的骨牌最多也只能影响到第i-1行，则容易得递推式：

**f\[****0****\]****\[1…11\]=1**

**f\[i\]\[s1\]=****∑f\[i-1\]\[****s2****\]**

其中(s1,s2)整体作为一个放置方案，可以把所有方案DFS预处理出来。下面讨论一下本题的一些细节。

首先讨论DFS的一些细节。对于当前行每一个位置，我们有3种放置方法：①竖直覆盖，占据当前格和上一行同一列的格；②水平覆盖，占据当前格和该行下一格；③不放置骨牌，直接空格。如何根据这些枚举出每个(s1,s2)呢？下面介绍两种方法：

第一种：

DFS共5个参数，分别为：p(当前列号)，s1、s2(当前行和上一行的覆盖情况)，b1、b2(上一列的放置对当前列上下两行的影响，影响为1否则为0)。初始时s1=s2=b1=b2=0。①p=p+1，s1=s1\*2+1，s2=s2\*2，b1=b2=0；②p=p+1，s1=s1\*2+1，s2=s2\*2+1，b1=1，b2=0；③p=p+1，s1=s1\*2，s2=s2\*2+1，b1=b2=0。当p移出边界且b1=b2=0时记录此方案。

第二种：

观察第一种方法，发现b2始终为0，知这种方法有一定的冗余。换个更自然的方法，去掉参数b1、b2。①p=p+1，s1=s1\*2+1，s2=s2\*2；②p=p+2，s1=s1\*4+3，s2=s2\*4+3；③p=p+1，s1=s1\*2，s2=s2\*2+1。当p移出边界时记录此方案。这样，我们通过改变p的移动距离成功简化了DFS过程，而且这种方法更加自然。

DFS过程有了，实现方法却还有值得讨论的地方。前面的例题中，我们为什么总是把放置方案DFS预处理保存起来？是因为不合法的状态太多，每次都重新DFS太浪费时间。然而回到这个题目，特别是当采用第二种时，我们的DFS过程中甚至只有一个判断(递归边界)，说明根本没有多少不合法的方案，也就没有必要把所有方案保存下来，对于每行都重新DFS即可，这不会增加运行时间却可以节省一些内存。

这个算法时间复杂度为多少呢？因为DFS时以两行为对象，每行2m，共进行n次DFS，所以是O(n\*4m)？根据“O”的上界意义来看并没有错，但这个界并不十分精确，也可能会使人误以为本算法无法通过1≤n、m≤11的测试数据，而实际上本算法可以瞬间给出m=10,n=11时的解。为了计算精确的复杂度，必须先算出DFS得到的方案数。

考虑当前行的放置情况。如果每格只有①③两个选择，则应该有2m种放置方案；如果每格有①②③这3个选择，且②中p只移动一格，则应该有3m种放置方案。然而现在的事实是：每格有①②③这3个选择，但②中p移动2格，所以可以知道方案数应该在2m和3m之间。考虑第i列，则其必然是：第i-1列采用①③达到；第i-2列采用②达到。设h\[i\]表示前i列的方案数，则得到h\[i\]的递推式：

**h\[0\]=1,h\[1\]=2**

**h\[i\]=2\*h\[i-1\]+h\[i-2\]**

应用组合数学方法求得其通项公式h\[m\]=。注意到式子的第二项是多个绝对值小于1的数的乘积，其对整个h\[m\]的影响甚小，故略去，得到方案数h\[m\]≈0.85\*2.414m，符合2m<h\[m\]<3m的预想。

因为总共进行了n次DFS，每次复杂度为O(h\[m\])，所以算法总时间复杂度为O(n\*h\[m\])=**O(n\*0.85\*2.414****m****)**，对m=10,n=11不超时也就不足为奇了。应用滚动数组，空间复杂度为O(2m)。

对于本题，我们已经有了公式和SCR两种算法。公式对于m\*n不是很大的情况有效，SCR算法在竞赛中记不住公式时对小的m、n有效。如果棋盘规模为n\*m(m≤10,n≤231-1)，则公式和SCR都会严重超时。有没有一个算法能在1分钟内解决问题呢？答案是肯定的，它仍然用到SC思想。

此算法中应用到一个结论：**给出一个图的邻接矩阵G(允许有自环，两点间允许有多条路径，此时G\[i\]\[j\]表示i到j的边的条数)，则从某点a走k步到某点b的路径数为G****k****\[a\]\[b\]**。本结论实际上是通过递推得到的，简单证明如下：从i走k步到j，必然是从i走k-1步到t，然后从t走1步到j，根据加法原理，即G\[k\]\[i\]\[j\]=∑G\[k-1\]\[i\]\[t\]\*G\[t\]\[j\]。是否感到这个式子很眼熟？没错，它和矩阵乘法一模一样，即：G\[k\]=G\[k-1\]\*G。因为矩阵乘法满足结合律，又由G\[1\]=G，所以我们得到结果：**G\[k\]=G****k**。

下面介绍这个算法。考虑一个有2m个顶点的图，每个顶点表示一行的覆盖状态，即SCR算法中的s1或s2。如果(s1,s2)为一个放置方案，则在s2和s1之间连一条(有向)边，则我们通过DFS一次可以得到一个邻接矩阵G。仍然按照逐行放置的思想来考虑，则要求我们每行选择一个覆盖状态，且相邻两行的覆盖状态(s1,s2)应为一个放置方案，一共有n行，则要求选择n个状态，在图中考虑，则要求我们从初始(第0行)顶点(1...111)n步走到(1…111)，因为图的邻接矩阵是DFS出来的，每条边都对应一个放置方案，所以可以保证走的每条边都合法。因此，我们要求的就是顶点(1…111)走n步到达(1…111)的路径条数。由上面的结论知，本题的答案就是Gn\[1…111\]\[1…111\]。

现在的问题是，如何计算G的n次幂？连续O(n)次矩阵乘法吗？不可取。矩阵的规模是2m\*2m，一次普通矩阵乘法要O((2m)3)=O(8m)，O(n)次就是O(n\*8m)，比SCR算法还要差得多。其实我们可以借用二分的思想。如果要计算38的值，你会怎么算呢？直接累乘将需要进行7次乘法。一种较简单的方法是：3\*3=32，32\*32=34，34\*34=38，只进行了3次乘法，效率高了许多。因为矩阵乘法满足结合律，所以可以用同样的思路进行优化。这种思路用递归来实现是非常自然的，然而，本题的矩阵中可能有210\*210=220=1048576个元素，如果用(未经优化的)递归来实现，将可能出现堆栈溢出。不过庆幸的是我们可以非递归实现。用bin\[\]保存n的二进制的每一位，从最高位、矩阵G开始，如果bin\[当前位\]为0，则把上一位得到的矩阵平方；如果为1，则平方后再乘以G。这种方法的时间复杂度容易算出：O(logn) 次矩阵乘法，每次O(8m)，共O(8m\*logn)。

这样对于m≤7就可以很快出解了。但对于m=n=8，上述算法都需要1s才能出解，无法令人满意。此算法还有优化空间。

我们的矩阵规模高达2m\*2m=4m，但是其中有用的(非0的)有多少个呢？根据介绍SCR算法时得到的h\[m\]计算式，G中有4m-h\[m\]=4m-0.85\*2.414m个0，对于m=8，可以算出G中98.5%的元素都是0，这是一个非常非常稀疏的矩阵，使用三次方的矩阵乘法有点大材小用。我们改变矩阵的存储结构，即第p行第q列的值为value的元素可以用一个三元组(p,q,value)来表示，采用一个线性表**依行列顺序**来存储这些非0元素。怎样对这样的矩阵进行乘法呢？观察矩阵乘法的计算式，当a\[i\]\[k\]或者b\[k\]\[j\]为0时，结果为0，对结果没有影响，完全可以略去这种没有意义的运算。则得到计算稀疏矩阵乘法的算法：**枚举a中的非0元素，设为(p,q,v1)，在b中寻找所有行号为q的非0元素(q,r,v2)，并把v1\*v2的值累加到c\[p\]\[r\]****中。**这个算法多次用到一个操作：找出所有行号为q的元素，则可以给矩阵附加一个数组hp\[q\]，表示线性表中第一个行号为q的元素的位置，若不存在则hp\[q\]=0。算出二维数组c之后再对其进行压缩存储即可。此矩阵乘法的时间复杂度为O()，在最坏情况下，a.not0=b.not0=4m，算法的复杂度为O(8m)，和经典算法相同。因为矩阵非常稀疏，算法复杂度近似为O(4m) 。考虑整个算法的时间复杂度：O(logn)次矩阵乘法，每次O(4m)，则总时间复杂度**O(logn\*4****m****)**，对于m≤9也可以很快出解了，对于m=10，n=2147483647，此算法在笔者机器上(Pm 1.6G，512M)运行时间少于20s。虽然仍然不够理想，但已经不再超时数小时。此算法空间复杂度为O(max\_not0+4m)，对于m=10，max\_not0小于190000。

以上给出了公式、SCR、矩阵乘方这3个算法，分别适用于不同的情况，本题基本解决。

读者应该已经注意到，覆盖模型和棋盘模型有很多共同点，譬如都是在矩形某些位置放入棋子(或某种形状的骨牌)来求方案数(如上例)或最优解(下面将会给出几个例题)。但不难看出，覆盖模型和棋盘模型又有着很大的不同：棋盘模型中，只要棋子所在的位置不被别的棋子攻击到即可，而覆盖模型中，棋子的攻击范围也不可以重叠。所以简单来说，**覆盖模型就是攻击范围也不能重叠的棋盘模型**。下面再给出一个与上例类似的覆盖模型的例题以加深印象。

【例6】

给出n\*m (1≤n、m≤9)的方格棋盘，用1\*2的矩形的骨牌和L形的(2\*2的去掉一个角)骨牌不重叠地覆盖，求覆盖满的方案数。

【分析】

观察题目条件，只不过是比例5多了一种L形的骨牌，因此很自然地顺着例5的思路走。本题中两种骨牌的最大长度和例5一样，所以仍然用f\[i\]\[s\]表示把前i-1行覆盖满、第i行覆盖状态为s的覆盖方案数，得到的递推式和例5完全一样：

**f\[****0****\]****\[1…11\]=1**

**f\[i\]\[s1\]=****∑f\[i-1\]\[****s2****\]**

其中(s1,s2)整体作为一个放置方案。例5中有两种DFS方案，其中第二种实现起来较第一种简单。但在本题中，新增的L形骨牌让第二种DFS难以实现，在例5中看起来有些笨拙的第一种DFS方案在本题却可以派上用场。回顾第一种DFS，我们有5个参数，分别为：p(当前列号)，s1、s2(当前行和对应的上一行的覆盖情况)，b1、b2(上一列的放置对当前列两行的影响，影响为1否则为0)。本题中，可选择的方案增多，故列表给出：

<table style="width:365.9pt;"> 
 <tbody> 
 <tr> 
 <td style="vertical-align:top;width:50.9pt;"> &nbsp; </td> 
 <td style="vertical-align:top;width:72pt;"> 覆盖情况 </td> 
 <td style="vertical-align:top;width:72pt;"> 条件 </td> 
 <td style="vertical-align:top;width:89.1pt;"> 参数s变化 </td> 
 <td style="vertical-align:top;width:81.9pt;"> 参数b变化 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:50.9pt;"> 1 </td> 
 <td style="vertical-align:top;width:72pt;"> 0 0 0 0 </td> 
 <td style="vertical-align:top;width:72pt;"> 无 </td> 
 <td style="vertical-align:top;width:89.1pt;"> s1=s1*2+b1 s2=s2*2+1-b2 </td> 
 <td style="vertical-align:top;width:81.9pt;"> b1=0 b2=0 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:50.9pt;"> 2 </td> 
 <td style="vertical-align:top;width:72pt;"> 0 0 1 1 </td> 
 <td style="vertical-align:top;width:72pt;"> b1=0 </td> 
 <td style="vertical-align:top;width:89.1pt;"> s1=s1*2+1 s2=s2*2+1-b2 </td> 
 <td style="vertical-align:top;width:81.9pt;"> b1=1 b2=0 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:50.9pt;"> 3 </td> 
 <td style="vertical-align:top;width:72pt;"> 1 0 1 0 </td> 
 <td style="vertical-align:top;width:72pt;"> b1=0 b2=0 </td> 
 <td style="vertical-align:top;width:89.1pt;"> s1=s1*2+1 s2=s2*2 </td> 
 <td style="vertical-align:top;width:81.9pt;"> b1=0 b2=0 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:50.9pt;"> 4 </td> 
 <td style="vertical-align:top;width:72pt;"> 1 0 1 1 </td> 
 <td style="vertical-align:top;width:72pt;"> b1=0 b2=0 </td> 
 <td style="vertical-align:top;width:89.1pt;"> s1=s1*2+1 s2=s2*2 </td> 
 <td style="vertical-align:top;width:81.9pt;"> b1=1 b2=0 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:50.9pt;"> 5 </td> 
 <td style="vertical-align:top;width:72pt;"> 0 1 1 1 </td> 
 <td style="vertical-align:top;width:72pt;"> b1=0 </td> 
 <td style="vertical-align:top;width:89.1pt;"> s1=s1*2+1 s2=s2*2+1-b2 </td> 
 <td style="vertical-align:top;width:81.9pt;"> b1=1 b2=1 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:50.9pt;"> 6 </td> 
 <td style="vertical-align:top;width:72pt;"> 1 1 0 1 </td> 
 <td style="vertical-align:top;width:72pt;"> b2=0 </td> 
 <td style="vertical-align:top;width:89.1pt;"> s1=s1*2+b1 s2=s2*2 </td> 
 <td style="vertical-align:top;width:81.9pt;"> b1=1 b2=1 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:50.9pt;"> 7 </td> 
 <td style="vertical-align:top;width:72pt;"> 1 1 1 0 </td> 
 <td style="vertical-align:top;width:72pt;"> b1=0 b2=0 </td> 
 <td style="vertical-align:top;width:89.1pt;"> s1=s1*2+1 s2=s2*2 </td> 
 <td style="vertical-align:top;width:81.9pt;"> b1=0 b2=1 </td> 
 </tr> 
 </tbody> 
</table>

容易看出，在本题中此种DFS方式实现很简单。考虑其复杂度，因为L形骨牌不太规则，笔者没能找到一维的方案数的递推公式，因此无法给出复杂度的解析式。但当m=9时，算法共生成放置方案79248个，则对于n=m=9,算法的复杂度为O(9\*79248)，可以瞬间出解。和上例一样，本题也没有必要保存所有放置方案，也避免MLE。

那么，对于本题是否可以应用上题的矩阵算法呢？答案是肯定的，方法也类似，复杂度为O(8m\*logn)。然而，对于本题却不能通过上题的稀疏矩阵算法加速，原因在于刚开始时矩阵中只有1-79248/49=70%的0，而运算结束后整个矩阵中只有2个0，根本无法达到加速效果。

由于有上题的铺垫，基本相同的本题也很快得到了解决。

【例7】

给出n\*m(n,m≤10)的方格棋盘，用1\*r的长方形骨牌不重叠地覆盖这个棋盘，求覆盖满的方案数。

【分析】

本题是例5的直接扩展。如果说例5中公式比SCR好，本题可以指出当公式未知时SCR依然是可行的算法。直接思考不容易发现方法，我们先考虑r=3时的情况。首先，**此问题有解当且仅当m或n能被3整除**。更一般的结论是：**用1\*r的骨牌覆盖满m\*n的棋盘，则问题有解当且仅当m或n能被r整除**。当r=2时，则对应于例5中m、n至少有一个是偶数的条件。此结论的组合学证明从略。

不同于例5，1\*3骨牌的“攻击范围”已经达到了3行，可以想象例5中的表示方法已经无法正确表示所有状态，但其思路依然可以沿用。例5中用f\[i\]\[s\]表示把前i-1行覆盖满、第i行覆盖状态为s的覆盖方案数，是因为当前行的放置方案至多能影响到上一行，状态中只要包含一行的覆盖状态即可消除后效性。本题中当前行的放置方案可以影响到上两行，故可以想到应保存两行的覆盖状态以消除后效性，即增加一维，用f\[i\]\[s1\]\[s2\]表示把前i-2行覆盖满、第i-1行覆盖状态为s1、第i行覆盖状态为s2的覆盖方案数。先不论上述表示方法是否可行(答案是肯定的)，r=2时状态有2维，r=3时有3维，推广后状态变量居然有r维，这样的方法不具有推广价值，而且空间复杂度也太高。

仔细分析上述方案，可以发现其失败之处。s1的第p位s1p为1(覆盖)时，s2p是不可能为0的(要求覆盖满)，则这两位(s1p, s2p)的(0,0),(0,1),(1,0),(1,1)四种组合中有一种不合法，而上述状态表示方法却冗余地保存了这个组合，造成空间复杂度过高，也进行了多余的计算。通过上面的讨论可以知道，每一位只有3种状态，引导我们使用三进制。我们用f\[i\]\[s\]表示把前i-2行覆盖满、第i-1和第i行覆盖状态为s的覆盖方案数，但这里状态s不再是二进制，而是三进制：sp=0表示s1p=s2p=0；sp=1表示s1p=0，s2p=1；sp=2表示s1p=s2p=1。这样，我们就只保留了必要的状态，空间和时间上都有了改进。当r=4时，可以类推，用四进制表示三行的状态，r=5时用五进制……分别写出r=2,3,4,5的程序，进行归纳，统一DFS的形式,可以把DFS(p,s1,s2)分为两部分：①for i=0 to r-1 do DFS(p+1,s1\*r+i,s2\*r+(i+1)mod r);②DFS(p+r,s1\*rr+rr-1,s2\*rr+rr-1) 问题解决。但DFS的这种分部方法是我们归纳猜想得到的，并没有什么道理，其正确性无法保证，我们能否通过某种途径证明它的正确性呢？仍以r=3为例。根据上面的讨论，sp取值0到2，表示两行第p位的状态，但sp并没有明确的定义。我们定义sp为这两行的第p位从上面一行开始向下连续的1的个数，这样的定义可以很容易地递推，递推式同上两例没有任何改变，却使得上述DFS方法变得很自然。

分析算法的时间复杂度，同例5一样需要用到DFS出的方案个数h\[m\]，并且仿照例5中h\[m\]的递推式，我们可以得到：

**h\[i\]=r****i****(i=0~r-1)**

**h\[j\]=r\*h\[j-1\]+h\[j-r\] (j=r~m)**

理论上我们可以根据递推式得到例5中那样的精确的通项公式，但需要解高于三次的方程，且根多数为复数，无法得到例5那样简单优美的表达式，这里仅给出r=2..5,m=10时h\[m\]的值依次为：5741，77772，1077334，2609585，9784376。对于推广后的问题，例5的矩阵算法依然可行，但此时空间将是一个瓶颈。

![20190205163142520.png][]

[20190205163142520.png]: /images/20220321/64ebfa2a8782418c8fb34b6d4958cce0.png