2022年状态压缩 .pdf

《2022年状态压缩 .pdf》由会员分享，可在线阅读，更多相关《2022年状态压缩 .pdf（12页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、状态压缩郑州 101 中学 /天津大学周伟第 1 页共 12 页状态压缩Abstract 信息学发展势头迅猛，信息学奥赛的题目来源遍及各行各业，经常有一些在实际应用中很有价值的问题被引入信息学并得到有效解决。然而有一些问题却被认为很可能不存在有效的(多项式级的 )算法，本文以对几个例题的剖析，简述状态压缩思想及其应用。Keywords 状态压缩、集合、 Hash、NPC Content Introduction 作为 OIers，我们不同程度地知道各式各样的算法。这些算法有的以O(logn)的复杂度运行， 如二分查找、 欧几里德 GCD 算法(连续两次迭代后的余数至多为原数的一半 )、平衡树，

2、有的以O(n )运行，例如二级索引、块状链表，再往上有 O(n)、O(nplogqn), 大部分问题的算法都有一个多项式级别的时间复杂度上界1，我们一般称这类问题2为 P 类(deterministic Polynomial-time)问题，例如在有向图中求最短路径。 然而存在几类问题， 至今仍未被很好地解决， 人们怀疑他们根 本 没 有 多 项 式 时 间 复 杂 度 的 算 法 ， 它 们 是NPC(NP-Complete) 和NPH(NP-Hard) 类，例如问一个图是否存在哈密顿圈(NPC)、问一个图是否 不存在哈密顿圈 (NPH)、 求一个完全图中最短的哈密顿圈(即经典的 Trave

3、ling Salesman Problem 货郎担问题， NPH)、在有向图中求最长 (简单)路径(NPH)，对这些问题尚 不 知 有 多 项 式 时间 的 算 法 存 在 。P 和 NPC 都 是 NP(Non-deterministic Polynomial-time)的子集， NPC 则代表了 NP 类中最难的一类问题，所有的NP 类问题都可以在多项式时间内归约到NPC 问题中去。 NPH 包含了 NPC 和其他一些不属于 NP(也更难 )的问题 (即 NPC 是 NP 与 NPH 的交集 )， NPC 问题的最优化版本一般是 NPH 的，例如问一个图是否存在哈密顿圈是NPC 的，但求最

4、短的哈密顿圈则是 NPH 的，原因在于我们可以在多项式时间内验证一个回路是否真的是哈密顿回路，却无法在多项式时间内验证其是否是最短的，NP 类要求能在多项式时间内验证问题的一个解是否真的是一个解，所以最优化TSP 问题不是NP 的，而是 NPH 的。存在判定性TSP 问题，它要求判定给定的完全图是否存在权和小于某常数v 的哈密顿圈，这个问题的解显然可以在多项式时间内验证，1请注意，大O 符号表示上界，即O(n)的算法可以被认为是O(n2)的，O(nplogqn)可以被认为是O(np+1)的。2在更正式的定义中，下面提到的概念都只对判定性问题或问题的判定版本才存在。Levin 给出了一个适用于非

5、判定问题的更一般的概念，但他的论文比Cook 的晚发表 2 年。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 12 页 - - - - - - - - - 状态压缩郑州 101 中学 /天津大学周伟第 2 页共 12 页因此它是 NP 的，更精确地说是NPC 的。1如上所述，对于 NPC 和 NPH 问题，至今尚未找到多项式时间复杂度的算法。然而它们的应用又是如此的广泛， 我们不得不努力寻找好的解决方案。 毫无疑问，对于这些问题， 使用暴力的搜索是可以得到正确的答案的，

6、但在信息学竞赛那有限的时间内，很难写出速度可以忍受的暴力搜索。例如对于TSP 问题，暴力搜索的复杂度是 O(n!)， 如此高的复杂度使得它对于高于10 的数据规模就无能为力了。那么，有没有一种算法，它可以在很短的时间内实现，而其最坏情况下的表现比搜索好呢？答案是肯定的状态压缩 (States Compression ，SC)。作为对下文的准备，这里先为使用Pascal的 OIers简要介绍一下 C/C+样式的位运算 (bitwise operation)。一、基本运算符名称C/C+样式Pascal样式简记法则按位与(bitwise AND) & and 全一则一否则为零按位或(bitwise

7、OR) | or 有一则一否则为零按位取反(bitwise NOT) not 是零则一是一则零按位异或(bitwise XOR) xor 不同则一相同则零以上各运算符的优先级从高到低依次为：,&,|二、特殊应用a)and：i.用以取出一个数的某些二进制位ii.取出一个数的最后一个1(lowbit)2：x&-x b)or ：用以将一个数的某些位设为1 c)not：用以间接构造一些数： 0=4294967295=232-1 d)xor：i.不使用中间变量交换两个数：a=ab;b=ab;a=ab; ii.将一个数的某些位取反有了这些基础，就可以开始了。1不应该混淆P、NP、NPC、NPH 的概念。这

8、里只是粗略介绍，详见关于算法分析的书籍，这会使新手读者的理论水平上一个台阶。弄不明白也没关系，基本不影响对本文其他部分的理解_ 2具有同样作用的还有(x-1)&xx,这个的道理更容易理解。lowbit 在树状数组 (某种数据结构 )中可以用到，这里不再单独介绍，感兴趣的可以参阅各牛的论文，或者加我QQ。建议掌握，否则可能会看不懂我的部分代码。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 12 页 - - - - - - - - - 状态压缩郑州 101 中学 /天津大学

9、周伟第 3 页共 12 页Getting Started 我们暂时避开状态压缩的定义，先来看一个小小的例题。【引例】1在 n*n(n20)的方格棋盘上放置n 个车(可以攻击所在行、列 )，求使它们不能互相攻击的方案总数。【分析】这个题目之所以是作为引例而不是例题，是因为它实在是个非常简单的组合学问题：我们一行一行放置，则第一行有n 种选择，第二行n-1，, ，最后一行只有 1 种选择，根据乘法原理， 答案就是 n!。这里既然以它作为状态压缩的引例，当然不会是为了介绍组合数学。我们下面来看另外一种解法：状态压缩递推(States Compressing Recursion,SCR)。我们仍然一行

10、一行放置。取棋子的放置情况作为状态，某一列如果已经放置棋子则为 1，否则为 0。这样，一个状态就可以用一个最多20 位的二进制数2表示。例如 n=5,第 1、3、4列已经放置，则这个状态可以表示为01101(从右到左 )。设 fs为达到状态 s的方案数，则可以尝试建立f 的递推关系。考虑 n=5,s=01101 。这个状态是怎么得到的呢？因为我们是一行一行放置的，所以当达到 s 时已经放到了第三行。 又因为一行能且仅能放置一个车，所以我们知道状态 s 一定来自：前两行在第3、4 列放置了棋子 (不考虑顺序，下同 )，第三行在第1 列放置；前两行在第 1、4 列放置了棋子，第三行在第3 列放置；

11、前两行在第 1、3 列放置了棋子，第三行在第4 列放置。这三种情况互不相交，且只可能有这三种情况。根据加法原理，fs应该等于这三种情况的和。写成递推式就是：f01101=f01100+f01001+f00101 根据上面的讨论思路推广之，得到引例的解决办法：f0=1 fs=fs 2i 其中 s0 , 01,1,11 ，s 的右起第 i+1 位为 1。3反思这个算法， 其正确性毋庸置疑 ( 可以和 n! 对比验证 ) 。但是算法的时间复杂度为 O (n2n)，空间复杂度 O(2n)，是个指数级的算法，比循环计算n! 差了好多，它有什么优势？较大的推广空间。4Sample Problems【例 1

12、】5在 n*n(n20)的方格棋盘上放置n 个车，某些格子不能放，求使它们不能互1本文所有例题的C+代码均可以在附件中找到。2方便、整齐起见，本文中不在数的后面标明进制。3考虑上节介绍的位运算的特殊应用，可以更精巧地实现。4还有一个很 的用处，即对新手说： “来看看我这个计算n!的程序，连这都看不懂就别OI 了”5题目来源：经典组合学问题。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 12 页 - - - - - - - - - 状态压缩郑州 101 中学 /天津大学周

13、伟第 4 页共 12 页相攻击的方案总数。【分析】对于这个题目，如果组合数学学得不够扎实，你是否还能一眼看出解法？应该很难。对于这个题目，确实存在数学方法(容斥原理 )，但因为和引例同样的理由，这里不再赘述。联系引例的思路，发现我们并不需要对算法进行太大的改变。引例的算法是在枚举当前行 (即 s 中 1 的个数，设为 r)的放置位置 (即枚举每个 1)，而对于例 1，第 r 行可能存在无法放置的格子， 怎么解决这个问题呢？枚举1 的时候判断一下嘛！事实的确是这样，枚举1 的时候判断一下是否是不允许放置的格子即可。但是对于 n=20，O(n2n)的复杂度已经不允许我们再进行多余的判断。所以实现这

14、个算法时应该应用一些技巧。对于第r 行，我们用 ar表示不允许放置的情况，如果某一位不允许放置则为1，否则为 0，这可以在读入数据阶段完成。运算时，对于状态 s，用 tmps=sar来代替 s进行枚举，即不枚举s 中的 1 转而枚举 tmps 中的 1。因为 tmps 保证了无法放置的位为0，这样就可以不用多余的判断来实现算法，代码中只增加了计算a数组和 r 的部分，而时间复杂度没有太大变化。这样，我们直接套用引例的算法就使得看上去更难的例1 得到了解决。你可能会说，这题用容斥原理更快。没错，的确是这样。但是，容斥原理在这题上只有当棋盘为正方形、放入的棋子个数为n、且棋盘上禁止放置的格子较少时

15、才有简单的形式和较快的速度。如果再对例1 进行推广，要在m*n 的棋盘上放置k个车，那么容斥原理是无能为力的，而SCR 算法只要进行很少的改变就可以解决问题1。这也体现出了引例中给出的算法具有很大的扩展潜力。棋盘模型是状态压缩最好的展示舞台之一。下面再看几个和棋盘有关的题目。【例 2】2给出一个 n*m 的棋盘 (n、m 80,n*m80)，要在棋盘上放 k(k20)个棋子，使得任意两个棋子不相邻。 每次试验随机分配一种方案， 求第一次出现合法方案时试验的期望次数，答案用既约分数表示。【分析】显然，本题中的期望次数应该为出现合法方案的概率的倒数，则问题转化为求出现合法方案的概率。 而概率=方案

16、总数合法方案数，方案总数显然为C(n*m,k) ，则问题转化为求合法方案数。整理一下，现在的问题是：在n*m 的棋盘上放 k 个棋子，求使得任意两个棋子不相邻的放置方案数。这个题目的状态压缩模型是比较隐蔽的。观察题目给出的规模，n、m 80，这个规模要想用 SC 是困难的，若同样用上例的状态表示方法(放则为 1，不放为0)，280无论在时间还是在空间上都无法承受。然而我们还看到n*m80，这种给出数据规模的方法是不多见的， 有什么玄机呢？能把状态数控制在可以承受的1如果这样改编，则状态的维数要增加，如有疑问可以参考下面的几个例子，这里不再赘述。2题目来源：经典问题改编。名师资料总结 - - -

17、精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 12 页 - - - - - - - - - 状态压缩郑州 101 中学 /天津大学周伟第 5 页共 12 页范围吗？稍微一思考，我们可以发现：9*9=8180，即如果 n,m 都大于等于 9，将不再满足 n*m80 这一条件。所以，我们有n 或 m 小于等于 8，而 28是可以承受的。我们假设mn(否则交换，由对称性知结果不变)n 是行数 m 是列数，则每行的状态可以用m 位的二进制数表示。但是本题和例1 又有不同：例 1 每行每列都只能放置一个

18、棋子， 而本题却只限制每行每列的棋子不相邻。但是，上例中枚举当前行的放置方案的做法依然可行。我们用数组s1.num1保存一行中所有的 num 个放置方案，则 s 数组可以在预处理过程中用DFS 求出，同时用 ci保存第 i 个状态中 1 的个数以避免重复计算。开始设计状态。如注释一所说，维数需要增加，原因在于并不是每一行只放一个棋子， 也不是每一行都要求有棋子，原先的表示方法已经无法完整表达一个状态。我们用fijk 表示第 i 行的状态为 sj且前 i 行已经放置了 k 个棋子2的方案数。沿用枚举当前行方案的做法，只要当前行的方案和上一行的方案不冲突即可，“微观”地讲，即ssnumi 和ssn

19、umi-1 没有同为 1 的位，其中 snumx表示第 x 行的状态的编号。然而，虽然我们枚举了第i 行的放置方案，但却不知道其上一行(i-1)的方案。为了解决这个问题，我们不得不连第i-1 的状态一起枚举，则可以写出递推式：f010=1; fijk=fi-1pk-cj 其中 s1=0 ，即在当前行不放置棋子； j 和 p 是需要枚举的两个状态编号，且要求 sj与 sp 不冲突，即 sj&sp=0。3当然，实现上仍有少许优化空间， 例如第 i 行只和第 i-1行有关，可以用滚动数组节省空间。有了合法方案数， 剩下的问题就不是很困难了， 需要注意的就只有 C(n*m,k)可能超出 64 位整数范

20、围的问题，这可以通过边计算边用GCD 约分来解决，具体可以参考附件中的代码。这个算法时间复杂度O(n*pn*num2) ，空间复杂度 ( 滚动数组)O(pn*num)，对于题目给定的规模是可以很快出解的。通过上文的例题，读者应该已经对状态压缩有了一些感性的认识。下面这个题目可以作为练习。【例 3】4在 n*n(n10)的棋盘上放 k 个国王 (可攻击相邻的 8 个格子 )，求使它们无法互相攻击的方案数。【分析】其实有了前面几个例子的分析，这个题目应该是可以独立解决的。不过既然确实有疑问，那我们就来分析一下。1运用简单的组合数学知识可以求出：在格数为m 的一行上放棋子且相邻两个棋子中间的空格不能

21、少于d的num=gm+d+1，其中 gi=1 (i=1.d+1); gj=gj-d-1+gj-1 (jd)。对于本题，num=144 。此式在下文也有应用。2为了避免歧义，下文中用pn 代替原题中的k。3请读者停下来仔细揣摩这个递推式，否则可能影响对本文后面内容的理解！4题目来源： SGU.223Little Kings 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 12 页 - - - - - - - - - 状态压缩郑州 101 中学 /天津大学周伟第 6 页共 1

22、2 页首先，你应该能想到将一行的状态DFS 出来(如果不能，请返回重新阅读，谢谢)， 仍然设为 s1.num,同时仍然设有数组c1.num记录状态对应的 1 的个数。和例 2 相同，仍然以 fijk 表示第 i 行状态为 sj，且前 i 行已经放置了 k 个棋子的方案数。递推式仍然可以写作：f010=1; fijk=fi-1pk-cj 其中仍要求 sj和 sp 不冲突。可是问题出来了：这题不但要求不能行、 列相邻，甚至不能对角线相邻！ sj、sp 不冲突怎么“微观地”表示呢？其实，稍微思考便可以得出方法：用sp分别和 sj、sj*2、sj/2进行冲突判断即可，原理很显然。解决掉这唯一的问题，接

23、下来的工作就没有什么难度了。算法复杂度同例2。下一个例题是状态压缩棋盘模型的经典题目，希望解决这个经典的题目能够增长你的自信。【例 4】1给出一个 n*m(n100,m10)的棋盘，一些格子不能放置棋子。求最多能在棋盘上放置多少个棋子，使得每一行每一列的任两个棋子间至少有两个空格。【分析】2显然，你应该已经有DFS 搜出一行可能状态的意识了(否则请重新阅读之前的内容 3 遍，谢谢 )，依然设为 s1.num,依旧有 c1.num保存 s中 1 的个数，依照例 1 的预处理搞定不能放置棋子的格子。问题是，这个题目的状态怎么选？继续像例2、3 那样似乎不行，原因在于棋子的攻击范围加大了。但是我们照

24、葫芦画瓢：例2、3 的攻击范围只有一格，所以我们的状态中只需要有当前行的状态即可进行递推，而本题攻击范围是两格，因此增加一维来表示上一行的状态。用 fijk 表示第 i 行状态为 sj、 第 i-1行状态为 sk时前 i 行至多能放置的棋子数，则状态转移方程很容易写出：fijk=maxfi-1kl+cj 其中要求 sj,sk,sl 互不冲突。因为棋子攻击范围为两格，可以直观地想象到num 不会很大。的确，由例2中得到的 num 的计算式并代入 d=2、m=10，得到 num=60。显然算法时间复杂度为 O(n*num3)，空间复杂度 (滚动数组 )O(num2)。此算法还有优化空间。我们分别枚

25、举了三行的状态， 还需要对这三个状态进行是否冲突的判断，这势必会重复枚举到一些冲突的状态组合。 我们可以在计算出s1.num后算出哪些状态可以分别作为两行的状态，这样在DP 时就不需要进行盲目的枚举。这样修改后的算法理论上比上述算法更优，但因为num 本身很小，所以这样修改没有显著地减少运行时间。值得一提的是，本题笔者的算法虽然在理论上并不是最优3，但由于位运算的使用，截至2 月 9 日，笔者的程序在PKU OJ 上长度最短，速度第二快。这个题目是国内比赛中较早出现的状态压缩题。它告诉我们状态压缩不仅可以像前几个例题那样求方案数， 而且可以求最优方案， 即状态压缩思想既可以应用到递推上 (SC

26、R)，又可以应用到DP 上(SCDP)，更说明其有广泛的应用空间。1题目来源： NOI2001 炮兵阵地；PKU.1185 2读者应该独立思考一个小时后再看分析，它值得这样。3有种应用三进制的方法理论上可能更优，但因为手工转换进制效率远不如系统的位运算高，且无法使用位运算判断可行性，程序效率并不比文中的高，故不再赘述那种方法。下文的一些题目将用到多进制。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 12 页 - - - - - - - - - 状态压缩郑州 101 中学

27、 /天津大学周伟第 7 页共 12 页看了这么多棋盘模型应用状态压缩的实例，你可能会有疑问，难道状态压缩只在棋盘上放棋子的题目中有用？不是的。我们暂时转移视线， 来看看状态压缩在其他地方的应用 覆盖模型 。【例 5】1给出 n*m (1n、m11)的方格棋盘，用 1*2 的长方形骨牌不重叠地覆盖这个棋盘，求覆盖满的方案数。【分析】这也是个经典的组合数学问题：多米诺骨牌完美覆盖问题(或所谓二聚物问题)。有很多关于这个问题的结论，甚至还有个专门的公式：如果m、n 中至少有一个是偶数， 则结果 =2211)1+n* j(cos4)1+m*i(4cos22mnij。这个公式形式比较简单，且计算的复杂度

28、是O(4* nm)的，很高效。但是这个公式内还有三角函数，且中学生几乎不可能理解，所以对我们能力的提高没有任何帮助。用SCR 算法能较好地解决这个问题。显然，如果n、m 都是奇数则无解 (由棋盘面积的奇偶性知 )，否则必然有至少一个解 (很容易构造出 )，所以假设 n、m 至少有一个偶数， 且 mn(否则交换 )。我们依然像前面的例题一样把每行的放置方案DFS 出来，逐行计算。用fis表示把前 i-1 行覆盖满、第 i 行覆盖状态为 s 的覆盖方案数。 因为在第 i 行上放置的骨牌最多也只能影响到第i-1 行，则容易得递推式：f01, 11=1 fis1= fi-1s2 其中(s1,s2) 整

29、体作为一个放置方案，可以把所有方案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*22， b1=b2=0；

30、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，1题目来源：经典问题；PKU.2411Mondriaans Dream2注意！第 i 行的放置方案用到第i-1 行的某格时， s2中该格应为0！名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - -

31、- - - - - - 名师精心整理 - - - - - - - 第 7 页，共 12 页 - - - - - - - - - 状态压缩郑州 101 中学 /天津大学周伟第 8 页共 12 页s1=s1*4+3，s2=s2*4+3；p=p+1，s1=s1*2，s2=s2*2+1。当 p 移出边界时记录此方案。这样，我们通过改变 p 的移动距离成功简化了DFS 过程，而且这种方法更加自然。DFS过程有了，实现方法却还有值得讨论的地方。前面的例题中，我们为什么总是把放置方案DFS 预处理保存起来？是因为不合法的状态太多，每次都重新 DFS 太浪费时间。然而回到这个题目，特别是当采用第二种时，我们的

32、DFS过程中甚至只有一个判断(递归边界 )，说明根本没有多少不合法的方案，也就没有必要把所有方案保存下来，对于每行都重新DFS 即可，这不会增加运行时间却可以节省一些内存。这个算法时间复杂度为多少呢？因为DFS 时以两行为对象，每行2m，共进行 n 次 DFS，所以是 O(n*4m)？根据“ O”的上界意义来看并没有错，但这个界并不十分精确，也可能会使人误以为本算法无法通过1n、m11的测试数据，而实际上本算法可以瞬间给出m=10,n=11 时的解。为了计算精确的复杂度，必须先算出 DFS 得到的方案数。考虑当前行的放置情况。如果每格只有两个选择，则应该有2m种放置方案；如果每格有这3 个选择

33、，且中p 只移动一格，则应该有3m种放置方案。然而现在的事实是：每格有这3 个选择，但中 p 移动 2 格，所以可以知道方案数应该在2m和 3m之间。考虑第 i 列，则其必然是：第i-1 列采用达到；第 i-2 列采用达到。设hi 表示前 i 列的方案数，则得到hi 的递推式：h0=1,h1=2hi=2*hi-1+hi-2 应用组合数学方法1求得其通项公式 hm=mm)21(422)21 (422。 注意到式子的第二项是多个绝对值小于1 的数的乘积，其对整个hm的影响甚小，故略去，得到方案数hm0.85*2.414m，符合 2mhm3m的预想。因为总共进行了n 次 DFS ，每次复杂度为O(h

34、m) ，所以算法总时间复杂度为 O(n*hm)= O(n*0.85*2.414m)，对 m=10,n=11不超时也就不足为奇了。应用滚动数组，空间复杂度为O(2m)。对于本题，我们已经有了公式和SCR 两种算法。公式对于m*n 不是很大的情况有效， SCR算法在竞赛中记不住公式时对小的m、n 有效。如果棋盘规模为n*m(m10,n231-1)，则公式和 SCR 都会严重超时。有没有一个算法能在1 分钟内解决问题呢2？答案是肯定的，它仍然用到SC 思想。此算法中应用到一个结论：给出一个图的邻接矩阵G(允许有自环，两点间允许有多条路径， 此时 Gij 表示 i 到 j 的边的条数 )，则从某点 a

35、 走 k 步到某点1特征方程等方法。这里不再赘述。2对于如此大的数据，高精度将成为瓶颈，故这里不考虑高精度的复杂度；我没有找到能1s 出解的算法，故延长时限到1min。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 12 页 - - - - - - - - - 状态压缩郑州 101 中学 /天津大学周伟第 9 页共 12 页b 的路径数为 Gkab1。本结论实际上是通过递推得到的，简单证明如下：从i走 k 步到 j，必然是从 i 走 k-1 步到 t，然后从 t 走 1

36、步到 j，根据加法原理，即Gkij= Gk-1it*Gtj2。 是否感到这个式子很眼熟？没错，它和矩阵乘法一模一样，即： Gk=Gk-1*G 。因为矩阵乘法满足结合律，又由G1=G，所以我们得到结果： Gk=Gk。下面介绍这个算法。考虑一个有2m个顶点的图，每个顶点表示一行的覆盖状态，即 SCR 算法中的 s1 或 s2。如果 (s1,s2)为一个放置方案，则在s2和 s1之间连一条 (有向 )边，则我们通过 DFS 一次可以得到一个邻接矩阵G。仍然按照逐行放置的思想来考虑， 则要求我们每行选择一个覆盖状态，且相邻两行的覆盖状态(s1,s2) 应为一个放置方案，一共有n 行，则要求选择n 个状

37、态，在图中考虑，则要求我们从初始 (第 0 行)顶点(1.111)n 步走到 (1111)，因为图的邻接矩阵是DFS 出来的，每条边都对应一个放置方案， 所以可以保证走的每条边都合法。因此，我们要求的就是顶点(1111) 走 n 步到达 (1111) 的路径条数。由上面的结论知，本题的答案就是Gn1 1111 111。现在的问题是，如何计算G 的 n 次幂？连续 O(n)次矩阵乘法吗？不可取。矩阵的规模是 2m*2m， 一次普通矩阵乘法要O(2m)3)=O(8m)， O(n)次就是 O(n*8m)，比 SCR 算法还要差得多。其实我们可以借用二分的思想。如果要计算38的值，你会怎么算呢？直接累

38、乘将需要进行7 次乘法。一种较简单的方法是：3*3=32，32*32=34，34*34=38，只进行了 3 次乘法，效率高了许多3。因为矩阵乘法满足结合律，所以可以用同样的思路进行优化。这种思路用递归来实现是非常自然的，然而，本题的矩阵中可能有210*210=220=1048576 个元素，如果用 (未经优化的 )递归来实现， 将可能出现堆栈溢出。 不过庆幸的是我们可以非递归实现。用 bin保存 n 的二进制的每一位，从最高位、矩阵G 开始，如果 bin当前位 为 0，则把上一位得到的矩阵平方；如果为1，则平方后再乘以G。这种方法的时间复杂度容易算出： O(logn) 次矩阵乘法，每次O(8m

39、)，共 O(8m*logn)。这样对于 m7就可以很快出解了。但对于m=n=8 ，上述算法都需要 1s 才能出解，无法令人满意。此算法还有优化空间。我们的矩阵规模高达2m*2m=4m，但是其中有用的 (非 0 的)有多少个呢？根据介绍 SCR 算法时得到的 hm计算式，G 中有 4m-hm=4m-0.85*2.414m个 0，对于m=8，可以算出 G 中 98.5%的元素都是 0，这是一个非常非常稀疏的矩阵，使用三次方的矩阵乘法有点大材小用。我们改变矩阵的存储结构， 即第 p 行第 q 列的值为 value的元素可以用一个三元组(p,q,value)来表示， 采用一个线性表 依行列顺序来存储这

40、些非 0 元素。 怎样对这样的矩阵进行乘法呢？观察矩阵乘法的计算式bkj*aikcij，当 aik 或者 bkj 为 0 时，结果为 0，对结果没有影响，完全可以略去这种没有意义的运算。则得到计算稀疏矩阵乘法的算法：枚举a 中的非 0 元素，设为 (p,q,v1)，在 b 中寻找所有行号为q 的非 0 元素(q,r,v2)，并把 v1*v2 的值累加到 cpr4中。这个算法多次用到一个操作：找出所有行号为 q 的元素，则可以给矩阵附加一个数组hpq，表示线性表中第一个行号为q的元素的位置，若不存在则hpq=0。算出二维数组 c 之后再对其进行压缩存储1上标表示乘幂。2因为 0 乘任何数都为0，

41、所以 Gk-1it或 Gtj 是否为 0 对最后的和没有影响。3这里假设大整数间的乘法和小整数间的乘法耗费同样的时间，实际上并非这样。但对于大数据，我们只关心结果 mod 某个常数的值，所以可以进行这样的假设。4此时 c 是个 2m*2m的二维数组名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 12 页 - - - - - - - - - 状态压缩郑州 101 中学 /天津大学周伟第 10 页 共 12 页即可。此矩阵乘法的时间复杂度为O(mmnotbnota420.*0

42、.)，在最坏情况下，a.not0=b.not0=4m，算法的复杂度为 O(8m)，和经典算法相同。 因为矩阵非常稀疏，算法复杂度近似为O(4m)1。考虑整个算法的时间复杂度：O(logn)次矩阵乘法，每次 O(4m)，则总时间复杂度O(logn*4m)，对于 m9 也可以很快出解了，对于m=10，n=2147483647，此算法在笔者机器上 (Pm 1.6G，512M)运行时间少于 20s。虽 然 仍 然 不 够 理 想 ， 但 已 经 不 再 超 时 数 小 时 。 此 算 法 空 间 复 杂 度 为O(max_not0+4m)，对于 m=10，max_not0小于 190000。以上给出了

43、公式、 SCR、矩阵乘方这 3 个算法，分别适用于不同的情况，本题基本解决。读者应该已经注意到，覆盖模型和棋盘模型有很多共同点，譬如都是在矩形某些位置放入棋子(或某种形状的骨牌 )来求方案数 (如上例 )或最优解 (下面将会给出几个例题 )。但不难看出，覆盖模型和棋盘模型又有着很大的不同：棋盘模型中，只要棋子所在的位置不被别的棋子攻击到即可，而覆盖模型中， 棋子的攻击范围也不可以重叠。 所以简单来说， 覆盖模型就是攻击范围也不能重叠的棋盘模型。下面再给出一个与上例类似的覆盖模型的例题以加深印象。【例 6】2给出 n*m (1n、m9)的方格棋盘，用1*2 的矩形的骨牌和L 形的 (2*2 的去

44、掉一个角 )骨牌不重叠地覆盖，求覆盖满的方案数。【分析】观察题目条件， 只不过是比例 5 多了一种 L 形的骨牌， 因此很自然地顺着例5 的思路走。本题中两种骨牌的最大长度和例5 一样，所以仍然用fis 表示把前 i-1 行覆盖满、第 i 行覆盖状态为 s 的覆盖方案数，得到的递推式和例5 完全一样：f01, 11=1 fis1=fi -1s2 其中(s1,s2) 整体作为一个放置方案。例5 中有两种 DFS方案，其中第二种实现起来较第一种简单。 但在本题中， 新增的 L 形骨牌让第二种 DFS难以实现， 在例5 中看起来有些笨拙的第一种DFS方案在本题却可以派上用场。 回顾第一种 DFS ，

45、我们有 5 个参数，分别为： p(当前列号 )，s1、s2(当前行和对应的上一行的覆盖情况)，b1、b2(上一列的放置对当前列两行的影响，影响为 1 否则为 0)。本题中，可选择的方案增多，故列表给出：1其实，虽然G 为很稀疏的矩阵，但乘方后非0 元素增多，不一定还是稀疏矩阵。但对于m=n=8，计算结束后，矩阵中仍然有80%的 0，上述算法仍然高效。此处的复杂度是理想情况。2题目来源： SGU.131Hardwood Floor名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页

46、，共 12 页 - - - - - - - - - 状态压缩郑州 101 中学 /天津大学周伟第 11 页 共 12 页覆盖情况条件参数 s 变化参数 b 变化1 0 0 0 0 无s1=s1*2+b1 s2=s2*2+1-b2 b1=0 b2=0 2 0 0 1 1 b1=0 s1=s1*2+1 s2=s2*2+1-b2 b1=1 b2=0 3 1 0 1 0 b1=0 b2=0 s1=s1*2+1 s2=s2*2 b1=0 b2=0 4 1 0 1 1 b1=0 b2=0 s1=s1*2+1 s2=s2*2 b1=1 b2=0 5 0 1 1 1 b1=0 s1=s1*2+1 s2=s2*

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

48、？答案是肯定的，方法也类似，复杂度为 O(8m*logn)。 然而，对于本题却不能通过上题的稀疏矩阵算法加速，原因在于刚开始时矩阵中只有1-79248/49=70% 的 0，而运算结束后整个矩阵中只有 2 个 0，根本无法达到加速效果。由于有上题的铺垫，基本相同的本题也很快得到了解决。【例 7】1给出 n*m(n,m10)的方格棋盘，用 1*r 的长方形骨牌不重叠地覆盖这个棋盘，求覆盖满的方案数。【分析】本题是例 5 的直接扩展。如果说例5 中公式比 SCR 好，本题可以指出当公式未知时 SCR 依然是可行的算法。直接思考不容易发现方法，我们先考虑r=3时的情况。首先， 此问题有解当且仅当m

49、或 n 能被 3 整除。更一般的结论是：用 1*r 的骨牌覆盖满 m*n 的棋盘，则问题有解当且仅当m 或 n 能被 r 整除。当r=2 时，则对应于例 5 中 m、n 至少有一个是偶数的条件。此结论的组合学证明从略。不同于例 5，1*3 骨牌的“攻击范围”已经达到了3 行，可以想象例5 中的表示方法已经无法正确表示所有状态，但其思路依然可以沿用。例5 中用 fis表示把前 i-1 行覆盖满、第 i 行覆盖状态为 s 的覆盖方案数，是因为当前行的放1题目来源：经典问题改编名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整

50、理 - - - - - - - 第 11 页，共 12 页 - - - - - - - - - 状态压缩郑州 101 中学 /天津大学周伟第 12 页 共 12 页置方案至多能影响到上一行，状态中只要包含一行的覆盖状态即可消除后效性。本题中当前行的放置方案可以影响到上两行，故可以想到应保存两行的覆盖状态以消除后效性，即增加一维，用fis1s2 表示把前 i-2 行覆盖满、第 i-1 行覆盖状态为 s1、 第 i 行覆盖状态为 s2的覆盖方案数。先不论上述表示方法是否可行(答案是肯定的 )，r=2 时状态有 2 维，r=3 时有 3 维，推广后状态变量居然有r 维，这样的方法不具有推广价值，而且