1、淺析倍增思想在信息學競賽中的應用,安徽省蕪湖市第一中學 朱晨光,引言,它的本質思想是,每次根據(jù)已經得到的信息，將考慮的范圍擴大一倍，從而加速操作。,倍增思想是一種十分巧妙的思想，在當今的信息學競賽中應用得十分廣泛。,引言,在解決信息學問題方面，倍增思想主要有這兩個方面的應用,一、在變化規(guī)則相同的情況下加速狀態(tài)轉移,二、加速區(qū)間操作,倍增思想應用之一在變化規(guī)則相同的情況下加速狀態(tài)轉移,首先，讓我們來看一個簡單的例子已知實數(shù)a，計算an。,很顯然，一種最簡單的方法就是令b=a，然后重復(n-1)次進行操作b=b*a.這樣，為了得到an，共進行了(n-1)次乘法。,現(xiàn)在考慮另外一種方法,例一,將n表

2、示成為二進制形式并提取出其中的非零位，即n=2b1+2b2+2bw，不妨設b1b2bw,由于已知 ，所以也就知道了 ，重復bw次將這個數(shù)平方并記錄下來，就可以得到(bw+1)個數(shù)： ， ， ，,根據(jù)冪運算的法則，可以推出 = = * * * * . 而這些數(shù)都已經被求出，所以最多再進行w次操作就可以得到,例一,由于n的二進制表示最多有 個非零位，所以bw最大為 。也就是說，最多進行O(log2n)次乘法就可以算出 ，這比進行O(n)次乘法效率高得多。,在實際情況中，a可能是一個實數(shù)，也可能是一個矩陣或是一個抽象的狀態(tài)。變化規(guī)則也可以是其他操作（如矩陣乘法、動態(tài)規(guī)劃的狀態(tài)轉移等）。但是只要符合以

3、下兩個條件，就可以應用倍增思想并采用類似于上面的方法加速計算：,小結一,一、每次的變化規(guī)則必須相同,二、變化規(guī)則必須滿足結合律,具體到上面的例子，每次的變化規(guī)則都是乘法，而乘法是滿足結合律的。,下面將通過例二更加深入地探討倍增思想在加速狀態(tài)轉移方面的應用，同時得到更精確的定義。,例二 骰子的運動,給定一個六個面的骰子，每個面上都有一定的權值（1到50之間的整數(shù)）。骰子運動的范圍是一個寬度為4，向左右無限延伸的帶子。帶子從左到右的橫坐標值為，-3，-2，-1，0，1，2，3，從前到后的縱坐標值依次為1，2，3，4。這樣，帶子被分成了無限多個格子。每個格子恰好能與骰子的一個面完全重合。骰子每次可以

4、向前后左右中的一個方向滾動一格，但不能移出帶子，花費是滾動后朝上的面所附帶的權值。,例二 骰子的運動,給定當前骰子位置的坐標與各個面的朝向，求將這個骰子移動到某個新位置所需的最小花費。（所給橫坐標的絕對值小于等于109）。,分析,如果不考慮橫坐標巨大的差值，本題完全可以用動態(tài)規(guī)劃求解。方法是將每一格按照骰子的朝向拆分成24種狀態(tài)，然后按列進行動態(tài)規(guī)劃得到最小花費。,具體方法是從起點所在列的24*4=96個狀態(tài)推到第二列96個狀態(tài)，再推到第三列，第四列，一直推到終點所在的列。每次都用Dijkstra算法算出從一列中某個狀態(tài)轉移到相鄰的一列中某個狀態(tài)的最小花費。時間復雜度是與橫坐標差值n是同階的。

5、,分析,但是，由于n最大可達109，所以這個算法無論從時間還是空間上都難以滿足要求。那么，是否可以采用倍增思想呢？,答案是肯定的！,下面，我們來驗證這里是否存在一種變化規(guī)則符合運用倍增思想的要求相同并符合結合律。,分析,設骰子從第1列某個狀態(tài)A運動到第2列某個狀態(tài)B最少需要花費代價c,則骰子從第2列的狀態(tài)A運動到第3列的狀態(tài)B同樣最少需要花費代價c！,這就是一種“相同的變化規(guī)則”！,更一般地，如果骰子從第i列某個狀態(tài)A運動到第(i+k)列某個狀態(tài)B最少需要花費代價c，則骰子從第j列的狀態(tài)A運動到第(j+k)列的狀態(tài)B也最少需要花費代價c.,分析,又由于前面所給出的算法是動態(tài)規(guī)劃，而動態(tài)規(guī)劃一個

6、很重要的特點是具有最優(yōu)子策略。,分析,至此，我們證明了變化規(guī)則既滿足相同性又滿足結合律，可以運用倍增思想解決：,分析,分析,*,*,*,分析,本題中，Dijkstra算法所耗費的時間可以看成是常數(shù)（根據(jù)題目中骰子各面權值的取值范圍可以算出必須考慮的點數(shù)為常數(shù)），每次倍增的時間為963，而倍增的次數(shù)為log2n，所以上述算法的時間復雜度為O(963log2N)。,小結二,從上題中，我們進一步加深了對倍增思想的理解，并且糾正了一個以前錯誤的認識：倍增思想所作用的對象實際上是變化規(guī)則，而并非具體的狀態(tài)！,倍增思想的作用是算出一個狀態(tài)到另一個狀態(tài)的變化量。也就是說，倍增思想計算出的量與具體的狀態(tài)是無關

7、的，而僅與狀態(tài)之間的關系有關。,小結二,將這個過程寫成偽代碼就是 ：,Doubling Algorithm(A,n) /a,b,c均為變化規(guī)則，a的初值由其他算法得到。如例2中a由Dijkstra算法得到 c=b=a; while (n) if (n%2) c=cb; b=bb; n/=2; B=A*c; return B; ,（A為原狀態(tài)，B為末狀態(tài)?！盃顟B(tài)*變化規(guī)則”的結果表示對于某個狀態(tài)施行變化規(guī)則后得到的狀態(tài)，“變化規(guī)則變化規(guī)則”的結果表示與依次施行兩個變化規(guī)則等價的變化規(guī)則。）,倍增思想應用之二 加速區(qū)間操作,在區(qū)間操作方面，有許多表現(xiàn)優(yōu)秀的算法與數(shù)據(jù)結構，線段樹便是其中的代表。這里

8、之所以提出倍增思想，是因為它也可以勝任在區(qū)間上的一些操作，并且在某些特定的情況下可以做得更好。,這里給出兩個應用倍增思想加速區(qū)間操作的經典實例：,例三 一般RMQ問題,給定N個整數(shù)A1N。每次詢問Axy中最小數(shù)的下標。,下面給出這個問題的ST(Sparse Table)算法,一般RMQ問題的ST算法,構造數(shù)組B，使得Bi,j表示Aii+2j-1中最小數(shù)的下標?？梢栽贠(Nlog2N)的時間內得到這個數(shù)組。然后對于每對i,j，令k= ，則比較ABi,k與ABj-2k+1,k的大小就可以得到結果了。每次詢問時間復雜度為O(1).,例四 構造后綴數(shù)組,給定一個長度為N的字符串，將它的N個后綴按字典序

9、排序。,通過記錄以每個字符開頭長len的字符串的排序結果，用基數(shù)排序O(N)地得到以每個字符開頭長2len的字符串的排序結果。總的時間復雜度為O(Nlog2N).,一個有趣的探討,倍增思想的本質是每次將考慮的范圍擴大一倍，那么是否可以每次擴大兩倍、三倍甚至更多呢？下面就來探討這個問題。,設每次將考慮的范圍擴大(k-1)倍(k=2)的倍增思想為k增思想，則本文所介紹的倍增思想為2增思想。,一個有趣的探討,對于k增思想，最多通過 次擴大就可以得到所有需要的值，這里為了討論方便，簡化為logkN. 但是，為了每次擴大(k-1)倍，必須操作(k-1)次。所以時間復雜度為O(k-1)logkN)。,本文

10、中k=2，因此復雜度為(2-1)log2N=log2N.,一個有趣的探討,為了將k=3與k=2進行比較。這里采用商值比較法：,一個有趣的探討,也就是說，當k3時f(k)為增函數(shù)，即恒有f(k)f(2)=0，即(k-1)-log2k0，k-1 log2k.,令f(k)=(k-1)-log2k.當k=2時，f(k)=0；當k3時f(k)=1- =1- 1- 0.51910,一個有趣的探討,y1=k-1,1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16,8 7 6 5 4 3 2 1 0,y2=log2k,k,y,一個有趣的探討,這就從數(shù)學角度解釋了倍增思想的高效性!,總結,倍增思想,應 用,加速狀態(tài)轉移,加速區(qū)間操作,恰當利用計算結果,不存在冗余的運算,高效,簡潔,獨辟蹊徑,總結,倍增思想,1，2，4，8，16，32，,在思考中體會內涵,在實戰(zhàn)中積累經驗,自然融入到思考過程中,指導自己解決各類問題,舉重若輕,揮灑自如,總結,紙上得來終覺淺,絕知此事要躬行,謝謝,謝謝大家！,歡迎提問！,應用之一的其他實現(xiàn)方法,當然，這個應用還有一些其他的實現(xiàn)方法。比如在計算an時,不一定要計算a1,a2,a4,a8，可以按照如下的規(guī)則進行遞歸：,很顯然，這種算法的時間復雜度也是O(log2N)，這也說明倍增思想在實際操作中是靈活多變的，要根據(jù)實際情況選擇相對簡便