第1章 利用快速冪提高冪運算效率

1.1 快速冪取模

1.1.1 快速冪取模的概念

設有整數a、自然數i，快速冪求解ai的思想就是每次把指數變小（指數除以2）、底數變大（進行底數平方運算），以減少運算次數，即：如果i是偶數，則，否則，。整數快速冪的程序段如下：

數論計算中有這樣一種運算：求一個數的冪對另外一個數的模的運算，即abmodn，其中a和b是非負整數，n是正整數。這樣的運算被稱為模取冪。在許多素數測試子程序和RSA公開密鑰加密系統中，模取冪運算是一種很重要的運算。所以，我們希望找到一種高效的方法來計算abmodn的值。

快速模取冪運算基于整數快速冪，即，用二進制來表示b時，采用反復平方法。設冪次b的二進制表示為(bk,bk-1,…,b1,b0)，即位長為k+1，其中bk為最高有效位，b0為最低有效位。快速模取冪運算的過程隨著a的冪值從0到b成倍增長，最終計算出ab%n，其程序段如下：

顯然，快速模取冪的算法復雜度為O(log2b)。

【1.1.1.1 Raising Modulo Numbers】

給出n對數字Ai和Bi(1≤i≤n)，以及一個整數M。請求解() modM。

輸入

輸入包含Z個測試用例，在輸入的第一行給出正整數Z。接下來給出每個測試用例。每個測試用例的第一行給出整數M(1≤M≤45000)，總和將除以這個數取余數；接下來的一行給出數字的對數H(1≤H≤45000)；接下來的H行，在每一行給出兩個被空格隔開的數字Ai和Bi，這兩個數字不能同時等于零。

輸出

對于每一個測試用例，輸出一行，是表達式() modM的結果。

試題來源：CTU Open 1999

在線測試：POJ 1995，ZOJ 2150

試題解析

本題可以基于整數快速冪和模運算規則，通過快速模取冪的算法求解。基本模運算規則如下：

在參考程序中，通過基于整數快速冪和模運算規則的快速模取冪函數modexp(a,b,m)求解ab%m。

參考程序

1.1.2 快速冪取模的應用

在快速冪取模的應用實驗中，加法原理和乘法原理被用于解題。

定理1.1.2.1（加法原理） 設A和B是有限集合S的兩個互不相交的子集，且A∪B=S，則|S|=|A|+|B|。

證明：集合S中的元素在子集A中的個數有|A|個，因為A和B互不相交，且A∪B=S，所以S中的元素不在A中必在B中，且B中的元素不在A中，則在S中不在A中的元素有|B|個，即|S|=|A|+|B|。■

例如，每天從上海到北京的高鐵車次有25次，民航航班有20班，則每天從上海到北京乘坐高鐵和民航的方式共有25+20=45（種）。

定理1.1.2.2（乘法原理） 設A和B是有限集合，|A|=p，|B|=q，則|A×B|=p×q。

例如，有2門數學課和4門計算機課，某學生要選數學課和計算機課各一門，則有2×4=8種選課方法。

【1.1.2.1 Teams】

從前有一種古老的游戲，這個游戲的特點是，每個隊的隊員數量沒有限制，只要隊中有隊長就行。（這個游戲完全是戰略性的，所以有時候玩家少了會增加獲勝的機會）。因此，有n名隊員，教練選擇k(1≤k≤n)名隊員參加比賽，并讓其中一人擔任隊長。給您的任務很簡單，只要找出一個教練可以用多少種方式從他的n名隊員中挑選一支參賽隊即可。這里要注意，隊員相同但隊長不同的參賽隊被認為是不同的隊伍。

輸入

輸入的第一行給出測試用例數T(T≤500)。接下來的T行每行給出n的值（1≤n≤109），即教練所擁有的隊員數量。

輸出

對于輸入的每一行，輸出測試用例的編號，然后給出可以以多少種方式選擇隊伍。請輸出答案模100000007的結果。有關確切的格式，請參見樣例輸入和樣例輸出。

試題來源：The first contest of the new season, 2009

在線測試：UVA 11609

試題解析

先從n名隊員中選k名隊員，再從k名隊員里選一個隊長，根據乘法原理，有C(n,k)×C(k, 1)種方式；又因為1≤k≤n，根據加法原理，選擇隊伍的方式數為。

因為C(n,k)×C(k,r)=C(n,r)×C(n-r,k-r)，其中k≥r，所以C(n,k)×C(k, 1)=C(n, 1)×C(n-1,k-1)，則，而為(1+1)n-1的展開式，所以選擇隊伍的方式數為n×2n-1。

參考程序通過快速冪取模運算求解2n-1%1000000007。

參考程序

【1.1.2.2 Key Set】

給出一個由n個整數{1, 2,…,n}組成的集合S。如果一個集合中的整數之和是偶數，則該集合被稱為鍵集（key set）。問：集合S中有多少非空子集是鍵集？

輸入

輸入給出多個測試用例。輸入的第一行給出一個整數T(1≤T≤105)，表示測試用例的個數。

對于每個測試用例，在一行中給出一個整數n(1≤n≤109)，表示集合中的整數數目。

輸出

對于每個測試用例，輸出鍵集數模100000007運算的結果。

試題來源：2015 Multi-University Training Contest 6

在線測試：HDOJ 5363

試題解析

本題給出一個由n個整數{1, 2,…,n}組成的集合S。問：集合S中有多少這樣的非空子集：子集里面所有元素的和為偶數？

在集合S中有n/2個偶數、(n+1)/2個奇數。要使S的子集里面所有元素的和為偶數，則在該子集中，偶數個數為0, 1, 2,…,n/2，奇數個數為偶數個。假設S中有a個偶數、b個奇數，則根據加法原理和乘法原理，S中元素和為偶數的子集數為(C(a, 0)+C(a, 1)+C(a, 2)+…+C(a,a))×(C(b, 0)+C(b, 2)+C(b, 4)+…+C(b, 2×(b/2)))。根據二項式定理以及推論，C(a, 0)+C(a, 1)+C(a, 2)+…+C(a,a)=(1+1)a=2a，C(b, 0)-C(b, 1)+C(b, 2)-C(b, 3)+…+(-1)bC(b,b)=(1-1)b=0，該二項式展開式中奇數項系數之和等于偶數項系數之和，所以C(b, 0)+C(b, 2)+C(b, 4)+…+C(b, 2×(b/2))=(1+1)b/2=2b-1。所以，S中元素和為偶數的子集數為2a+b-1，即2n-1。

又因為鍵集是非空的子集，所以要去掉C(a, 0)×C(b, 0)的情況。本題要求對鍵集數模100000007運算的結果，所以最終結果為(2n-1-1) mod 100000007。由于結果比較大，因此通過快速冪取模進行計算。

參考程序

【1.1.2.3 Turn the pokers】

暑假，Alice在家里待了很長時間，無所事事。她出去買了m張撲克牌，打算玩撲克。但她不想玩傳統的游戲，想要改變。她把這些撲克牌面朝下，然后，把撲克牌翻轉n遍，每遍她能翻轉Xi張撲克牌。她想知道能得到多少種結果。你能幫她解決這個問題嗎？

輸入

輸入給出若干測試用例。

每個測試用例第一行給出兩個非負整數n(n>0)和m(m≤100000)。接下來的一行給出n個整數Xi(0≤Xi≤m)。

輸出

對于每個測試用例，在一行中輸出對答案數進行模1000000009運算的結果。

提示

對于第2個樣例，0表示牌面向下，1表示牌面向上。初始時狀態為000。第一個結果為000→111→001→110，第二個結果為000→111→100→011，第三個結果為000→111→010→101。因此，有3種結果（110, 011, 101）。

試題來源：2014 Multi-University Training Contest 1

在線測試：HDOJ 4869

試題解析

對于撲克牌，0表示牌面向下，1表示牌面向上。初始時牌面都向下。如果最后有x張牌的牌面向上，一共有m張撲克牌，這種情況對答案的貢獻為C(m,x)。所以要知道最后可能的牌面向上的牌數。

每次翻轉撲克牌的張數Xi是確定的。如果Xi為奇數，那么這次翻轉后1的個數的增量一定是奇數（增量可以是負奇數）；同理，如果Xi為偶數，那么這次翻轉后1的個數的增量也一定是偶數（增量可以是負偶數）。所以，如果所有Xi的和為奇數，則最后的牌面向上的牌數是奇數；同理，如果所有Xi的和為偶數，則最后的牌面向上的牌數也是偶數。設所有翻轉完成后，牌面向上的牌數最小是L，最大是R，牌面向上的牌數為L+2，L+4，…，R-2也都是可以達到的，而且L和R一定是同奇偶的。根據加法原理，最后可能的牌面向上的牌數為C(m,L)+C(m,L+2)+…+C(m,R-2)+C(m,R)。

因此，首先要確定L和R。

計算牌面向上的最小牌數L，就是計算最小的1的數目，每次都盡可能多地把1轉化為0；而計算牌面向上的最大牌數R，就是計算最大的1的數目，每次都盡可能多地把0轉化為1。可以用兩組if語句分別確定L和R。

第一組if語句確定L。

●如果當前牌面向上的最小牌數L大于或等于現在翻牌的數量Xi，即L≥Xi，就把Xi張牌面向上的牌翻轉，也就是把1變成0，則L=L-Xi；

●如果當前牌面向上的最小牌數L小于現在翻牌的數量Xi，而牌面向上的最大牌數R大于或等于本次翻牌的數量Xi，即L<Xi≤R，因為翻牌數量在上下限之間，所以可以把當前牌面朝上的牌的數量變為0或1（不是絕對能變為0，因為有可能當前牌面向上的牌數為奇數，而翻牌的次數是偶數），所以要判斷L和Xi的奇偶性是否一樣，如果一樣，則牌面向上的最小牌數L變為0，否則變為1。

●如果當前牌面向上的最大牌數R小于現在翻牌的數量Xi，即R<Xi，則在把1全部變為0的同時，還有Xi-R個0變為1，即L=Xi-R。

第二組if語句確定R。

●如果當前牌面向上的最大牌數R和現在翻牌的數量Xi的和沒有超過總牌數m，即R+Xi≤m，則把Xi張牌面向下的牌翻轉，0變成1，這樣使1最多，即R=R+Xi。

●如果當前牌面向上的最大牌數R和現在翻牌的數量Xi的和超過總牌數m，而如果當前牌面向上的最小牌數L和現在翻牌的數量Xi的和沒有超過總牌數m，即L+Xi≤m<R+Xi，則要判斷L+Xi和m的奇偶性是否相同，如果相同，則新狀態中必定所有牌的牌面都朝上，即全是1，R=m，如果不同，則R=m-1。

●如果當前牌面向上的最小牌數L和現在翻牌的數量Xi的和超過總牌數m，即L+Xi>m，把m個1變成0，那么還要翻L+Xi-m張牌，最終得到m-(L+Xi-m)個1，所以R=2m-L-Xi。

在確定L和R之后，計算C(m,L)+C(m,L+2)+…+C(m,R-2)+C(m,R)。

因為，所以，。用數組c表示組合數C(m,i)，則c[0]=1，c[i]=c[i-1]×(m-i+1)/i。本題要求對結果進行模1000000009運算。根據費馬小定理，如果p是素數、a是正整數，且GCD(a,p)=1，則ap-1≡1(modp)。所以和ap-2模p同余。設p=1000000009，c[i]=c[i-1]×(m-i+1)%p×ip-2%p。所以，需要通過快速冪取模運算求解。

參考程序