算法合集之《浅析倍增思想在信息学竞赛中的应用》

浅析倍增思想在信息学竞赛中的应用安徽省芜湖市第一中学朱晨光第1页共29页浅析倍增思想在信息学竞赛中的应用安徽省芜湖市第一中学朱晨光目录摘要...............................................................................................2关键字...........................................................................................2正文...............................................................................................2引言........................................................................................2应用之一在变化规则相同的情况下加速状态转移........2应用之二加速区间操作.....................................................8一个有趣的探讨..................................................................11总结.............................................................................................12感谢.............................................................................................13参考文献.....................................................................................13附录.............................................................................................13浅析倍增思想在信息学竞赛中的应用安徽省芜湖市第一中学朱晨光第2页共29页摘要倍增思想是解决信息学问题的一种独特而巧妙的思想。本文就倍增思想在信息学竞赛中两个方面的应用进行了分析。全文可以分为五个部分：第一部分引言，简要阐述了倍增思想的重要作用以及运用方法；第二部分介绍倍增思想的第一个应用——在变化规则相同的情况下加速状态转移；第三部分介绍倍增思想的第二个应用——加速对区间进行的操作；第四部分探讨了一个有趣的问题，即为什么倍增思想每次只将考虑范围扩大一倍而不是两倍、三倍等；第五部分总结全文，再次指出倍增思想的重要性以及应该怎样灵活运用倍增思想。关键字倍增思想变化规则状态转移区间操作正文引言倍增思想是一种十分巧妙的思想，在当今的信息学竞赛中应用得十分广泛。尽管倍增思想可以应用在许多不同的场合，但总的来说，它的本质是：每次根据已经得到的信息，将考虑的范围扩大一倍，从而加速操作。大家所熟悉的归并排序实际上就是倍增思想的一个经典应用。在解决信息学问题方面，倍增思想主要有这两个方面的应用——一、在变化规则相同的情况下加速状态转移；二、加速区间操作。下文将就这两个方面进行详细的讨论。倍增思想应用之一在变化规则相同的情况下加速状态转移1首先，让我们来看一个简单的例子——已知实数a，计算a17。分析：很显然，一种最简单的方法就是令b=a，然后重复16次进行操作b=b*a.这样，为了得到a17，共进行了16次乘法。1这里是指由一种状态变化到另一种状态，并不只限于动态规划中的“状态转移”。浅析倍增思想在信息学竞赛中的应用安徽省芜湖市第一中学朱晨光第3页共29页现在考虑另外一种方法，令a0=a,a1=a2,a2=a4,a3=a8,a4=a16,可以看出，ai=ai-12,(1=i=4)。于是，得到a0,a1,a2,a3,a4共需要4次乘法。而a17=a*a16=a0*a4,也就是说，再进行一次乘法就可以得到a17.这样，总共进行5次乘法就算出了a17.如果将这种方法推而广之，就可以解决这样一个一般性的例题：例1、已知a，计算na:分析：1、将n表示成为二进制形式并提取出其中的非零位，即n=2b1+2b2+……+2bw，不妨设b1b2……bw.2、由于已知a，所以也就知道了02a，重复bw次将这个数平方并记录下来，就可以得到(bw+1)个数：02a，12a，22a，……，bwa2；3、根据幂运算的法则，可以推出na=bwbba22221=12ba*22ba*……*bwa2，而这些数都已经被求出，所以最多再进行(bw+1)次操作就可以得到na。由于n的二进制表示最多有1log2n个非零位，所以bw最大为n2log。也就是说，最多进行O(n2log)次乘法就可以算出na，这比进行O(n)次乘法效率高得多。当然，由于得到n的二进制表示的过程本身就是按照从低位到高位的顺序，所以并不需要记录02a，12a，22a，……，bwa2，只需要每次即算即用就可以了。伪代码如下（见下页）：那么，这个算法是如何减少乘法次数的呢？显然，na=bwbba22221=12ba*22ba*……*bwa2使得求na转化为求不超过1log2n个a的幂的积。而序列02a，12a，22a，……，bwa2中除了第一个数以外，每一个数都是前一个数的平方。即在从ia2得到12ia的过程中，按照原始的方法需要进行2i次乘法操作，而现在只需要利用已知结果ia2进行一次乘法操作（ia2*ia2=12ia）即可。大大减少了操作次数，从而降低了时间复杂度。浅析倍增思想在信息学竞赛中的应用安徽省芜湖市第一中学朱晨光第4页共29页而在实际情况中，a可能是一个实数，也可能是一个矩阵或是一个抽象的状态。变化规则也可能是其他操作（如矩阵乘法、动态规划的状态转移等）。但是只要符合以下两个条件，就可以应用倍增思想并采用类似于上面的方法加速计算：1、每次的变化规则必须相同；2、变化规则必须满足结合律。具体到上面的例子，每次的变化规则都是乘法，而乘法是满足结合律的。下面将通过另一个例子更加深入地探讨倍增思想在加速状态转移方面的应用，同时得到更精确的定义。例2、骰子的运动2给定一个六个面的骰子，每个面上都有一定的权值（1到50之间的整数）。骰子运动的范围是一个宽度为4，向左右无限延伸的带子（如图1.1）。带子从左到右的横坐标值为……，-3，-2，-1，0，1，2，3，……，从前到后的纵坐标值依次为1，2，3，4（这里的坐标对应的都是格子，而不是点）。这样，带子被分成了无限多个格子。每个格子恰好能与骰子的一个面完全重合。骰子每次可以向前后左右中的一个方向移动一格（但不能移出带子），花费是移动后朝上的面所附带的权值。2CEPC2003ProblemDDiceContestlongdoublepower(longdoublea,longn){longdoubleb,result;result=1;b=a;while(n){if(n%2)result*=b;b*=b;n/=2;}returnresult;}算法1.1浅析倍增思想在信息学竞赛中的应用安徽省芜湖市第一中学朱晨光第5页共29页给定当前骰子位置的坐标与各个面的朝向，求将这个骰子移动到某个新位置所需的最小花费。（所给横坐标的绝对值小于等于109）。分析：如果不考虑横坐标巨大的差值，本题完全可以用动态规划求解。方法是将每一格按照骰子的朝向拆分成24种状态，然后按列进行动态规划（本质上是一个分层图）得到最小花费。具体方法是从第一列24*4=96个状态推到第二列96个状态，再推到第三列，第四列……，一直推到终点所在的列，每次都用Dijkstra算法算出从一列中某个状态转移到相邻的一列中某个状态的最小花费。时间复杂度是与横坐标差值n是同阶的。但是，由于n最大可达109，所以这个算法无论从时间还是空间上都难以满足要求。那么，是否可以采用倍增思想呢？答案是肯定的。下面，我们来验证这里是否存在一种变化规则符合运用倍增思想的要求——相同并符合结合律。设骰子从第1列某个状态A运动到第2列某个状态B需要花费代价c,则骰子从第2列的状态A（与前一个A的行号以及朝向均相同）运动到第3列的状态B同样需要花费代价c！这就是一种“相同的变化规则”！更一般地，如果骰子从第i列某个状态A运动到第(i+k)3列某个状态B需要花费代价c，则骰子从第j列某个状态A运动到第(j+k)列某个状态B也需要花费代价c，这就是相同的变化规则。又由于前面所给出的算法是动态规划，而动态规划一个很重要的特点是具有最优子策略。所以如图1.2中按照A-B-C的顺序计算转移费用再加起来（对于一条路径来说，最小费用是它在这三个部分中的最小费用之和）与按照B-C-A的顺序计算转移费用再加起来完全一样，因为它们相互独立，而且合并方式是加法，所以符合结合律。3这里k可以是正数或负数，表示向右或向左运动4…………132-2-10123…………………………………………图1.1浅析倍增思想在信息学竞赛中的应用安徽省芜湖市第一中学朱晨光第6页共29页图1.2至此，我们证明了变化规则既满足相同性又满足结合律，可以运用倍增思想解决：（以下默认终点在起点的右侧，如果是在左侧，处理方法类似；如果在同一列，用Dijkstra算法就可以得到答案）1、用Dijkstra算法得到一列中某个状态A转移到右边相邻一列中某个状态B所需最小花费。这可以推出一个96*96的矩阵，不妨称为a1;2、根据已经得到的变化规则a1可以计算出一列中某个状态A转移到右边与其距离为2的一列中某个状态B所需花费——a2。3、依次类推得到a4，a8，a16，a32，……,aw(w=n且2wn);4、与例1相类似，设n=2b1+2b2+……+2bw，然后从初始状态（即起点所在的那一列）开始，不断对其施行变化规则12ba、22ba、……、bwa2，最终得到从起点到终点所在那一列每个状态的最小花费。本题中，Dijkstra算法所耗费的时间可以看成是常数（根据题目中骰子各面权值的取值范围可以算出必须考虑的点数为常数），每次倍增的时间为963，而倍增的次数为log2n，所以上述算法的时间复杂度为O(963log2N)。从上题中，我们进一步加深了对于倍增思想的理解，并且纠正了一个以前错误的认识：倍增思想所作用的对象实际上是变化规则，而并非具体的状态！倍增思想的作用是算出一个状态到另一个状态的变化量。设初始状态为A，目标状态为B，A到B的变化量为c，则最终结果是A*c（这里的乘号表示一种变化的手段）。也就是说，倍增思想计算出的量与具体的状态是无关的，而仅与状态之间的关系有关。将这个过程写成伪代码就是（见下页）：阶段ⅠA段B段C段阶段Ⅱ阶段Ⅲ阶段Ⅳ阶段Ⅴ浅析倍增思想在信息学竞赛中的应用安徽省芜湖市第一中学朱晨光第7页共29页an=1，an=an/2*an/2n为偶数，a(n-1)/2*a(n-1)/2*an为奇数.DoublingAlgorithm(A,n){//a,b,c均为变化规则，a的初值由其他算法得到。如例2中a由Dijkstra算法得到c=b=a;while(n){if(n%2)c=c•b;b=b•b;n/=2;}B=A*c;returnB;}算法1.2（A为原状态，B为末状态。“状态*变化规则4”的结果表示对于某个状态施行变化规则后得到的状态，“变化规则•变化规则”的结果表示与依次施行两个变化规则等价的变化规则。）可以看出，算法1.2与算法1.1十分相似。其实，算法1.1就是算法1.2的一个实例。需要再次强调的是，这里的变化规则必须是相同