優先隊列

普通的隊列是一種先進先出的數據結構，元素在隊列尾追加，而從隊列頭刪除。優先隊列是一種按照優先級決定出隊順序的數據結構，優先隊列中的每個元素被賦予級別，隊首元素的優先級最高。

例如：4入隊，1入隊，3入隊，此時隊首元素不是4而是1，這是因為默認最小的元素優先級最高。此時如果選擇出隊，那么是1出隊。

優先隊列的實現方法有很多，最簡單常見的是利用“堆”這個數據結構來實現。所以我們先從堆排序開始講起。

堆排序

堆排序是指利用堆這種數據結構所設計的一種排序算法。堆是一個近似完全二叉樹的結構，并同時滿足堆積的性質：即子結點的鍵值或索引總是小于（或者大于）它的父節點。

使用堆排序對一組數進行排序，主要分為2步：

建堆，復雜度O(n)，建堆的過程類似體育比賽中的淘汰賽，兩個一組進行淘汰，選出優勝者。然后再對優勝者分組，兩個一組進行淘汰...直到只剩下唯一的優勝者。整個過程需要比較?n/2+n/4+n/8+...次，所以復雜度為O(n)。

從堆頂逐個取出元素，并對堆進行維護，每次取值并維護的復雜度為O(log(n))，因此堆排序的總復雜度為O(nlog(n))。

大根堆

能夠用來做優先隊列的數據結構有很多，平衡樹，二項堆，左偏樹，斐波那契堆......我們只介紹最簡單的大根堆。

大根堆利用了與堆排序類似的方法。建堆后每次可以用?\(O(log(n))\)?的時間取出最大數。

堆的存儲及建堆

直接使用數組來存儲堆，我們始終將?\(a_n\)?和?\(a_{n/2}\)?中較大的數，放在?\(a_{n/2}\)?的位置上。

添加堆元素

直接將新的元素放在最后一個位置上\(a_n\)，同時按照建堆時的方法，比較\(a_n\)和\(a_{n/2}\)?，\(a_{n/2}\)和\(a_{n/4}\)，... 這樣可以在\(O(log(n))\)的復雜度維護好堆。

堆取最大

直接讀取\(a_0\)，復雜度\(O(1)\)?。

堆刪除最大

刪除最大值需要維護堆，這個復雜度是\(O(log(n))\)?的。

	取最大	添加	刪除最大
數組	\(O(n)\)	\(O(1)\)	\(O(n)\)
鏈表	\(O(n)\)	\(O(1)\)	\(O(n)\)
排序好的數組	\(O(1)\)	\(O(n)\)	\(O(1)\)
大根堆	\(O(1)\)	\(O(log(n))\)	\(O(log(n))\)

stl的優先隊列

雖然我們講了很多大根堆的知識，但實際并不需要我們手寫一個大根堆，\(C++\)?的\(Stl\)?中直接提供了可以調用的優先隊列，?\(Stl\)?中的優先隊列就是采用大根堆來實現的。

使用優先隊列

//優先隊列需要頭文件 ?

#include<queue> ?// 定義優先隊列 ?

priority_queue<結構類型> 隊列名; ?

priority_queue <int> q; ?

priority_queue <double> d; ?//優先隊列的操作 ?

q.size();//返回q里元素個數 ?

q.empty();//返回q是否為空，空則返回1，否則返回0 ?

q.push(k);//在q的末尾插入k ?

q.pop();//刪掉q的第一個元素 ?

q.top();//返回q的第一個元素

以上如何使用?\(stl\)?中的優先隊列？以下為具體示例。

#include<cstdio> ?

#include<queue> ?

using?namespace?std;

priority_queue <int> q;

int?main(){

????q.push(10), q.push(8), q.push(12), q.push(14), q.push(6);

????while?(!q.empty()) {

????????cout?<< q.top() << " ";

????????q.pop();

???}

}

程序大意就是在這個優先隊列里依次插入?\(10、8、12、14、6\)?，再輸出。

輸出的結果就是：14 12 10 8 6

也就是說，它是按從大到小排序的！

less和greater優先隊列

還是以?\(int\)?為例，先來聲明：

priority_queue <int,vector<int>,less<int> > p; ?

priority_queue <int,vector<int>,greater<int> > q;

\(less\)?是從大到小，?\(greater\)?是從小到大。

結構體優先隊列

要想使用結構體的優先隊列， 需要在結構體內部重載小于號。

struct?node??{ ?

????int?x, y; ?

????bool?operator?< (const?node & a) const??????{ ?

????????return?x<a.x; ?

????} ?

};

一個node結構體有兩個成員，x和y，它的小于規則是x小者小。

它也是按照重載后的小于規則，從大到小排序的。

priority_queue <node> q;

int?main(){

????k.x = 10, k.y = 100; q.push(k);

????k.x = 12, k.y = 60; q.push(k);

????k.x = 14, k.y = 40; q.push(k);

????k.x = 6, k.y = 80; q.push(k);

????k.x = 8, k.y = 20; q.push(k);

????while?(!q.empty()) ???{

????????node m = q.top(); q.pop();

????????printf("(%d,%d) ", m.x, m.y);

????}

}

程序大意就是插入(10,100),(12,60),(14,40),(6,20),(8,20)(10,100),(12,60),(14,40),(6,20),(8,20)?這五個node

再來看看它的輸出：(14,40) (12,60) (10,100) (8,20) (6,80)

就是按照x從大到小排序的。

除了重載運算符之外，還有一種方法可以自定義結構體如何比較大小，這需要自己定義一個新的結構體，專門用作比較。

struct?node?{

????int?to, cost;

};//定義一個專門用作比較的結構體

struct?cmp?{

????bool?operator() (node a, node b) {

????????return?a.cost > b.cost;

????}

};

priority_queue<node,vector<node>, cmp> priq;

哈夫曼編碼與哈夫曼樹

哈夫曼編碼

哈夫曼編碼（Huffman?Coding），又稱霍夫曼編碼，是一種編碼方式，哈夫曼編碼是可變字長編碼（VLC）的一種。Huffman于1952年提出一種編碼方法，該方法完全依據字符出現概率來構造異字頭的平均長度最短的碼字，有時稱之為最佳編碼，一般就叫做?Huffman編碼。

哈夫曼編碼可以用來做無損的文件壓縮，我們常用的?zip,rar,7z等壓縮算法，都用到了哈夫曼編碼，而哈夫曼編碼思想的本質是貪心算法。具體原理是這樣的，我們日常用到的所有文件，存儲在硬盤上的每一個字節（8?bit），都可以表示為0?255的一個數字。反過來，保存這個數字需要一個字節的空間。但這些數字出現的頻率是不一樣的，有的高有的低。于是我們想有沒有方法，讓出現頻率高的數字編碼長度短一些，讓出現頻率低的數字，編碼長度長一些，這樣占用的總空間就變小了。

編碼	占用多少bit
10	2
11	2
000	3
001	3
010	3
0110	4
0111	4

哈夫曼編碼保證所有編碼的前綴都不相同，這樣就可以保證不同的原始數據一定編碼成不同的哈夫曼碼。反過來做解碼的過程中，能夠明確知道每一個編碼的結束位置，方便快速解碼。如果我們把編碼中的?0,10,1?看作樹的節點，那么恰好對應一顆二叉樹，這就是哈夫曼樹。

哈夫曼樹

給定N個權值作為N個葉子結點，構造一棵二叉樹，若該樹的帶權路徑長度達到最小，稱這樣的二叉樹為最優二叉樹，也稱為哈夫曼樹?(Huffman?Tree)。哈夫曼樹是帶權路徑長度最短的樹，權值較大的結點離根較近。

以本圖為例，綠色的是最終的葉子節點，節點上的數字，是點的權值Wi，我們可以理解為編碼出現的次數。而葉子結點到根結點的距離?Li可以理解為編碼的長度。而整個樹的權值等于所有Wi×Li的和，我們可以理解為總的編碼長度。

按照本圖的分配方法，整棵樹的權值為：(2+4)×5+7×4+(8+12+19)×3+(20+30)×2=275

這是一個最優的編碼方式。構造哈夫曼樹，需要配合一個優先隊列來實現。

什么是單調隊列

單調隊列，即單調遞減或單調遞增的隊列。單調隊列與單調棧十分類似， 都是單增單減， 唯一的區別在于彈出元素時， 棧只能在棧頂將后進的元素彈出，而單調隊列則可以在隊列兩端都進行元素的彈出， 在尾部實現元素的插入, 單調隊列實際上是應用了雙端隊列的屬性。

圖中，企圖插隊的人戰斗力為?6，隊尾的5，1?都小于它，而6?和它戰斗力相同，它憑著插隊的一股勁，把這三個人全部擠掉，到了7的后面。

這就是所謂的單調隊列了，隊列元素保持單調遞增（減），而保持的方式就是通過插隊，把隊尾破壞了單調性的數全部擠掉，從而使隊列元素保持單調。

單調隊列的出現可以簡化問題，隊首元素便是最大（小）值，這樣，選取最大（小）值的復雜度便為?O(1)，由于隊列的性質，每個元素入隊一次，出隊一次，維護隊列的復雜度均攤下來便是O(1)?。

單調隊列VS單調棧

單調隊列和單調棧的相同點

單調隊列和單調棧的“頭部”都是最先添加的元素，“尾部”都是最后添加的元素。

遞增和遞減的判斷依據是：從棧底（隊尾）到棧頂（隊首），元素大小的變化情況。所以隊列和棧是相反的。

它們的操作是非常相似的。當隊列長度為無窮大時，遞增的單調隊列和遞減的單調棧，排列是一樣的！

原因在于，長度為無窮大的的隊列不會在“頭部”有popfront操作，而在“尾部”的操作是一模一樣的：數據都從“尾部”進入，并按照相同的規則進行比較。

兩者維護的時間復雜度都是O(n)，因為每個元素都只操作一次。

單調隊列和單調棧的不同點

隊列可以從隊列頭彈出元素，可以方便地根據入隊的時間順序（訪問的順序）刪除元素。單調隊列和單調棧維護的區間不同。當訪問到第?i個元素時，單調棧維護的區間為[0,i)?，而單調隊列維護的區間為?(front,i)單調隊列可以訪問“頭部”和“尾部”，而單調棧只能訪問棧頂（也就是“尾部”）。這導致單調棧無法獲取?[0,i)的區間最大值/最小值。

二進制GCD

我們之前已經學習過如何利用輾轉相除法求兩個數的最大公約數。這里我們再講一個利用二進制求解Gcd的方法。

二進制Gcd計算當中共有4種情況：

a,b為偶數，則Gcd(a,b)=2×Gcd(a/2,b/2)?。

a為奇數，b為偶數，則Gcd(a,b)=Gcd(a,b/2)。

a,b為奇數。假設a>=b，則?Gcd(a,b)=Gcd((a?b)/2,b)。

a為0，則返回b。

ll gcd(ll a, ll b) {

????if?(a == 0)

????????return?b;

????if?(b == 0)

????????return?a;

????if?(!(a & 1) && !(b & 1))

????????return?2?* gcd(a >> 1, b >> 1);

????else?if?(!(a & 1))

????????return?gcd(a >> 1, b);

????else?if?(!(b & 1))

????????return?gcd(a, b >> 1);

????else

????????return?gcd(abs(a - b), min(a, b));

}

二進制Gcd只使用位移和加減法實現，因此運行效率較高，尤其在求高精大數的Gcd時，效率提高明顯，這是因為大數除法的實現很復雜。

模運算與快速冪

模運算及性質

模運算多應用于程序編寫中。%的含義為求余。模運算在數論和程序設計中都有著廣泛的應用，從奇偶數的判別到素數的判別，從模冪運算到最大公約數的求法，從孫子問題到凱撒密碼問題，無不充斥著模運算的身影。

性質
(a×b×c)%p=((a×b)%p×c)%p	正確	可以避免大數運算
(a×b)%p=(a%p)×(b%p)	錯誤	(5×5)%3
(a×b)%p=((a%p)×(b%p))%p	正確
(a×b)%p=(b×a)%p	正確
(ab)%p=b%pa%p	錯誤	(42)%3
(a+b)%p=(a%p)+(b%p)	錯誤	(5+5)%3
(a+b)%p=((a%p)+(b%p))%p	正確

快速冪

快速冪，顧名思義，就是可以比較快的求出x的y次冪。

通常我們要求x的y次冪復雜度是O(y)的，就是循環y次，每次乘x。但實際上我們可以將復雜度降低到O(log(y))的級別，用到的是二進制的性質以及冪指數的性質。

首先我們可以將y表示成2的冪次的和，形如y=2p1+2p2+2p3...的形式。

比如:22=16+4+2（?22對應的二進制是10110)

那么x22=x16×x4×x2由于是二進制，很自然地想到用位運算這個強大的工具：&和?>>。&?運算通常用于二進制取位操作。一個數?&1的結果就是取二進制的最末位。>>?運算比較單純，二進制去掉最后一位。

通過代碼來詳細講解快速冪的思想：

int?fastPow(int?x, int?y) {

????int?ans = 1;

????while?(y != 0) {

???????if?(y & 1) ans = ans * x;

????????x = x * x;

????????y >>= 1;

????}

????return?ans;

}

首先我們要理解x=x×x在做什么，x×x=x2,x2×x2=x4,...所以x?值的的變化就是x?>x2?>x4?>x8?>x16....。

剛才的例子中的y為22需要的就是?x22=x16×x4×x2?。

所以每次判斷y最低位是否為1，如果為1則將答案乘上當前的x。每次y都右移一位。直到y為0。

通常情況下xy的答案都很大，遠遠超過long?long的數據范圍，需要對答案mod一個較大的質數。因此我們討論快速冪主要是討論xy%p的結果。在+和*運算中， mod符號的位置不影響最終答案，所以可以在快速冪的運算過程中直接對ans和x直接做mod處理。

**注意：**快速冪求模運算，并不要求模數為質數，任意數都可以套用這個方法。

遞推和遞歸的區別

在學習動態規劃之前， 我們先復習一下之前學過的遞推和遞歸。

• 從程序上看，遞歸表現為自己調用自己，它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復計算，大大地減少了程序的代碼量。

• 遞歸是從問題的最終目標出發，逐漸將復雜問題化為簡單問題，最終求得問題。遞推則是由已知答案推出要求的問題。

如何分析遞推式

遞推的思想有些類似數學中常用的數學歸納法，我們假設知道1?>(n?1)的所有的答案，看如何推導出n的答案。

搜索中的記憶化

記憶化搜索

我們在之前的課程中曾經提到過記憶化搜索，記憶化搜索就是在搜索時記錄一些有用的答案， 我們遞歸的本質就是在搜索答案，但是有些問題會被重復的搜索，所以我們就可以用空間換時間的思想， 將被搜索的問題的答案記錄下來， 當下一次再被搜索到這個問題的時候， 就可以在O(1)?的時間給出答案。

int?ans[1005];

int?F(int?n) {

????if?(n == 1?|| n == 2) return?1;

????if?(ans[n] == 0) ans[n] = F(n - 1) + F(n - 2);

????return?ans[n];

}

記憶化搜索實際上就是在搜索過程中不做重復的計算，遇到相同的搜索分支直接調用上次的計算結果。記憶化搜索是實現動態規劃強有力的方法之一，另外一種實現動態規劃的方法就是遞推，在后面的章節中會詳細講解。

記憶化搜索的適用范圍

根據記憶化搜索的思想，它是解決重復計算，而不是重復生成，也就是說，這些搜索必須是在搜索擴展路徑的過程中分步計算的題目，也就是“搜索答案與路徑相關”的題目，而不能是搜索一個路徑之后才能進行計算的題目，必須要分步計算。

動態規劃的狀態與轉移

動態規劃與貪心

多階段逐步解決問題的策略就是按一定順序或一定的策略逐步解決問題的方法。分解的算法策略也是多階段逐步解決問題策略的一種表現形式，主要是通過對問題逐步分解，然后又逐步合并解決問題的。貪心算法每一步都根據策略得到一個結果，并傳遞到下一步，自頂向下，一步一步地做出貪心決策。

動態規劃算法的每一步決策給出的不是唯一結果，而是一組中間結果，而且這些結果在以后各步可能得到多次引用，只是每走一步使問題的規模逐步縮小，最終得到問題的一個結果。

貪心算法

貪心選擇性質：在求解一個問題的過程中，如果再每一個階段的選擇都是當前狀態下的最優選擇，即局部最優選擇，并且最終能夠求得問題的整體最優解，那么說明這個問題可以通過貪心選擇來求解，這時就說明此問題具有貪心選擇性質。

最優子結構性質：當一個問題的最優解包含了這個問題的子問題的最優解時，就說明該問題具有最優子結構。

動態規劃

最優化原理：如果問題的最優解所包含的子問題的解也是最優的，就稱該問題具有最優子結構，即滿足最優化原理。

無后效性：即某階段狀態一旦確定，就不受這個狀態以后決策的影響。也就是說，某狀態以后的過程不會影響以前的狀態，只與當前狀態有關。

有重迭子問題：即子問題之間是不獨立的，一個子問題在下一階段決策中可能被多次使用到。

優勢：采用動態規劃方法，可以高效地解決許多用貪心算法或分治算法無法解決的問題。但貪心算法也有它的優勢：構造貪心策略不是很困難，而且貪心策略一旦經過證明成立后，它就是一種高效的算法。

分治與減治

分治法是很多高效算法的基礎，如排序算法（快速排序，歸并排序），快速傅立葉變換等等。

結合一些經典的分治問題，來深入理解分治的思想，并利用主定理分析這些問題的算法復雜度。

對一個分治算法進行復雜度分析時，首先設T(n)表示對規模為n的數據進行分治的復雜度，再列出T(n)有關的遞推關系式，之后判斷是否適用主定理，如果適用則應用主定理的對應情形進行求解。

算法描述

對于一個長度為n的序列，要找出其中第k大的元素，我們可以首先在序列中任意取出一個數x，將比x小的數作為一個新序列，記作序列1。

將比x大的數作為另一個新序列，記作序列2。

假設比x大的數的個數為cnt1c，與x相等的數的個數為cnt2，假設cnt1≥k說明第k大的元素在序列1中，我們遞歸的在序列1中找第k大的元素。假設cnt1<k且cnt1+cnt2≥k，說明第k大的元素為x，直接返回答案即可。否則如果cnt1+cnt2<k，說明第k大的元素在序列2中，遞歸在序列2中找即可，不過在原序列中第k大的元素，在序列2中則為第k?cnt1?cnt2大的元素，因此我們應該在序列2中遞歸去找第k?cnt1?cnt2的元素。

算法流程梳理如下： 在序列中隨機取出一個數x將比x小的數劃分為序列1，比x大的數劃分為序列2，假設比x大的數個數為cnt1，與x相等的數的個數為cnt2如果k≤cnt1在序列1中遞歸找第k大的元素；否則如果k≤cnt1+cnt2?說明x就是第k大的元素，直接返回答案；否則在序列2中遞歸找第k?cnt1?cnt2?大的元素。

solve(l, r, k){//表示對數組a中區間[l,r]的數找第k大

????x = a[l + rand() % (r - l + 1)];

????L = l, R = r;

????for?(i = l; i <= r; i++)

????????if?(a[i] < x)

????????????tmp[L++] = a[i];

????????else?if?(a[i] > x)

tmp[R--] = a[i];

????cnt1 = r - R, cnt2 = R - L + 1；

????if?(cnt1 >= k)

????????return?solve(R + 1, r, k);

????else?if?(cnt1 + cnt2 >= k)

????????return?x;

????else

????????return?solve(l, L - 1, k - cnt1 - cnt2);

}

算法實現

#define N 200020

using?namespace?std;

int?n, k, a[N];

int?tmp[N];

int?solve(int?l, int?r, int?k)//表示對數組a中區間[l,r]的數找第k大

{

????int?x = a[l + rand() % (r - l + 1)];

????int?L = l, R = r;

????for?(int?i = l; i <= r; i++)

???????if?(a[i] < x) ???????????tmp[L++] = a[i];

????????else?if?(a[i] > x) ???????????tmp[R--] = a[i];

????int?cnt1 = r - R, cnt2 = R - L + 1;

????if?(cnt1 >= k) ???????return?solve(R + 1, r, k);

????else?if?(cnt1 + cnt2 >= k) ???????return?x;

????else?????????return?solve(l, L - 1, k - cnt1 - cnt2);

int?main(){

????srand(time(0));

????cin?>> n >> k;

????for?(int?i = 1; i <= n; i++)

????????cin?>> a[i];

????solve(1, n, k);

}

復雜度分析

首先，用和快速排序一樣的想法估計算法復雜度。

由于我們每次是隨機從當前區間取出一個數，那么平均意義下小于它和大于它的數的個數近乎相等，遞歸求解時，無論遞歸哪邊，下次處理的數據規模減半。因此，設求解長為n的序列的第k大時間復雜度為T(n)。

那么，T(n)=T(n/2)+O(n)。不難得到T(n)=O(n)T(n)=O(n)。但事實上，更嚴謹的來講：

T(n)=O(n)+(T(n?1)+T(n?2)+...+T(k)+T(n?k)+...+T(n?1))/nT(n)=O(n)+(T(n?1)+T(n?2)+...+T(k)+T(n?k)+...+T(n?1))/n

我們上面已經估計了T(n)=O(n)，就只要驗證猜想。

不妨假設當k<n時，存在常數t滿足T(k)≤tk那么：

T(n)≤O(n)+(t/n)?(n?1+n?2+...+k+n?k+...+n?1)

于是有：

T(n)≤O(n)+(t/n)?((n+k?1)(n?k)/2+(2n?k?1)k/2)

進而得到

T(n)≤O(n)+(t/2n)?(n2?n?2k2+2nk)=O(n)+t/2?(n?1?2k2/n+2k)

所以，?T(n)=O(n)

nth-element

事實上，C++給我們提供了一個叫做nth_element的函數，可以在O(n)時間復雜度內求一個數組中第k小的數。

它的用法是：nth_element(a+l,a+l+k-1,a+r)

這樣會使得a數組中區間[l,r)（注意是左閉右開區間）中第k小的元素處在第k個位置上，也即a[l+k?1]。

int?main( ?) {

????static?int?a[15] = {0, 1, 2, 5, 7, 3, 4, 1};

nth_element(a + 1, a + 4, a + 8);

????for?(int?i = 1; i <= 8; i++) {

????????printf("%d ", a[i]);

????????printf("\n");

????}

????return?0;}

karatsuba乘法

Karatsuba乘法是一種快速乘法。此算法在1960?年由Anatolii?Alexeevitch?Karatsuba提出，并于1962年得以發表。 此算法主要用于兩個大數相乘。普通乘法的復雜度是O(n2)，而Karatsuba算法的復雜度僅為O(nlog3)，約為?O(n1.585)（?log3是以2?為底）。Karatsuba算法應用了分治的思想。

算法描述

假設我們有A,B兩個大數，都為n位，要計算A?B，需要將A,B劃分成兩等份，如下圖所示：

將A分成a1和a0兩等份，將B分成b1和b0兩等份，長度都為n/2?。那么有：

A=a1×10n/2+a0

B=b1×10n/2+b0

A×B=c2×10n+c1×10n/2+c0

其中：

c2=a1×b1c2=a1×b1

c1=a0×b1+b0×a1c1=a0×b1+b0×a1

c0=a0×b0c0=a0×b0

對于長度為n的兩個數相乘，我們設其復雜度為T(n)。

我們是將其劃分為四個長度為n/2的兩個數進行遞歸乘法運算，之后進行三次加法進行求解。

因此T(n)=4?T(n/2)+O(n)。

應用主定理求解T(n)，a=4,b=2,d=1，logba=2>d，因此T(n)=O(nlogb?a)=O(n2)?。

總的復雜度并無變化。

對于?c1=a0×b1+b0×a1，將其繼續轉化為c1=(a1+a0)?(b1+b0)?(c2+c0)?。

在這個運算中，有4次加法，只有1次乘法。

通過轉換，原來需要計算4次(n/2)2?的乘法，現在只需要計算3?次，其余依靠加減法來計算。

這便是Karatsuba乘法分治的核心思路。

#define sz(s) int(s.size())
#define super vector<int>
namespace integer {using super = vector<int>;const int base_digits = 9;const int base = 1000000000;super& trim(super& a) {while (!a.empty() && a.back() == 0) a.pop_back();return a;}int compare(const super& lhs, const super& rhs) {int cmp = sz(lhs) - sz(rhs), i = sz(lhs) - 1;if (cmp != 0) return cmp < 0 ? -1 : 1;while (i != -1 && lhs[i] == rhs[i]) i--;return i == -1 ? 0 : lhs[i] < rhs[i] ? -1 : 1;}inline void norm(int& a, int& k) {k = (a < 0 ? (a += base, -1) : a < base ? 0 : (a -= base, 1)); }super add(const super& lhs, const super& rhs) {super res=(sz(rhs) < sz(lhs) ? lhs : rhs);super bit=(sz(rhs) < sz(lhs) ? rhs : lhs);res.push_back(0);int i = 0, k = 0;for (; i < sz(bit); i++) norm(res[i] += k + bit[i], k);for (; i < sz(res) && 0 < k; i++) norm(res[i] += k, k);return trim(res); }super sub(super res, const super& bit) {int i = 0, k = 0;for (; i < sz(bit); i++) norm(res[i] += k - bit[i], k);for (; i < sz(res) && k < 0; i++) norm(res[i] += k, k);return trim(res);}string to_string(super a) {string res = "";if (a.empty()) return "0";static char s[10];sprintf(s, "%d", a.back());res.append(s);for (int i = sz(a) - 2; ~i; i--) {sprintf(s, "%09d", a[i]);res.append(s);}return res;}super to_super(string s) {super res;for (int i = sz(s), x; 0 < i; i -= base_digits) {const char* p = s.c_str() + max(0, i - base_digits);if (i != sz(s)) s[i] = '\0';sscanf(p, "%09d", &x);res.push_back(x);}return trim(res);}#define int64 long long#define vll vector<int64>super convert_base(const super& a, int old_digits, int new_digits) {vll p(max(old_digits, new_digits) + 1);for (int i = p[0] = 1; i < sz(p); i++)p[i] = p[i - 1] * 10;super res;int64 cur = 0;for (int i = 0, cur_digits = 0; i < sz(a); i++) {cur += a[i] * p[cur_digits];cur_digits += old_digits;while (new_digits <= cur_digits) {res.push_back(cur % p[new_digits]);cur_digits -= new_digits;cur /= p[new_digits]；} }res.push_back(cur);return trim(res);}vll karatsuba(const vll& a, const vll& b) {int n = sz(a);vll res(n + n);if (n <= 32) {for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)res[i + j] += a[i] * b[j];return res; }int k = n >> 1;vll a1(a.begin(), a.begin() + k);vll a2(a.begin() + k, a.end());vll b1(b.begin(), b.begin() + k);vll b2(b.begin() + k, b.end());vll a1b1 = karatsuba(a1, b1);vll a2b2 = karatsuba(a2, b2);for (int i = 0; i < k; i++) a2[i] += a1[i];for (int i = 0; i < k; i++) b2[i] += b1[i];vll r = karatsuba(a2, b2);for (int i = 0; i < sz(a1b1); i++) r[i] -= a1b1[i];for (int i = 0; i < sz(a2b2); i++) r[i] -= a2b2[i];for (int i = 0; i < sz(r); i++) res[i + k] += r[i];for (int i = 0; i < sz(a1b1); i++) res[i] += a1b1[i];for (int i = 0; i < sz(a2b2); i++) res[i + n] += a2b2[i];return res; }super mul(const super& lhs, const super& rhs) {const int new_digits = 6;const int base = 1000000;super a6(convert_base(lhs, base_digits, new_digits));super b6(convert_base(rhs, base_digits, new_digits));vll a(a6.begin(), a6.end());vll b(b6.begin(), b6.end());while (sz(a) < sz(b)) a.push_back(0);while (sz(b) < sz(a)) b.push_back(0);if (sz(a) == 0) return super();while (sz(a) & (sz(a) - 1))a.push_back(0), b.push_back(0);vll c(karatsuba(a, b));super res;int64 k = 0;for (int i = 0; i < sz(c); i++) {int64 p = c[i] + k;res.push_back(p % base);k = p / base;}res = convert_base(res, new_digits, base_digits);return trim(res); }}
using namespace integer;
istream& operator >> (istream& in, super& p) {string s; in >> s;p = to_super(s);return in;}
ostream& operator << (ostream& out, super p) {return out << to_string(p);}
int main() {ios::sync_with_stdio(false);super a, b;cin >> a >> b;cout << mul(a, b) << endl;return 0;}

Hash散列

Hash一般翻譯做散列或音譯為哈希，是把任意長度的輸入通過散列算法變換成固定長度的輸出，該輸出就是散列值。這種轉換是一種壓縮映射，也就是，散列值的空間通遠小于輸入的空間。例如：我們可以將一個文件的特征提取出來，通過某種方法的計算得到一個long?long?的值，這就是文件的?Has?值。對于兩個不同的文件，如果Hash值相同，則可能這兩個文件是一樣的（不一定），如果兩個文件的?Hash值不同，則肯定是不一樣的。因此?Hash本身允許我們建立一種?Key和?Value的結構，Hash值是Key?，具體的文件內容是?Value。如果?Hash值計算的足夠巧，并且數值范圍足夠大，那么如果兩個文件的Hash?值相同，這兩個文件相同的概率可能高達99.9999999999999%。在網絡時代，兩個不同的人比較他們的文件是否相同，無需將整個文件傳給對方，只需二人分別計算一個足夠大的Hash,比如21024，然后比較兩個文件的Hash?值就好了。

數值Hash

根據之前所學，我們可以用一個map來保存這些數字，如果有相等的，可以直接判斷。map提供了一種紅黑樹結構，可以讓所有數字維持有序，時間復雜度為O(nlog(n))。

我們還可以直接對這些數字排序，然后遍歷判斷前后兩個數字是否相等，時間復雜度為O(nlog(n))。

曾經使用數組來記錄一個數字是否存在，但對于long?long，我們做不到把ai當做數組下標訪問，考慮用一個方法把這些數變得更小，簡單來說我們找一個大于n的質數p，然后用ai%p當做ai的?Hash值，然后我們就可以用一個大小為p的vector?數組記錄 所有ai。這相當于將?%p相等的數分到同一個組里（vector），按照這種方法，平均一個組中只有1,2個數，我們只需要在組內比較是否有相同的數字即可。這個的平均復雜度為O(n)。

這里需要注意一點，Hash只能判斷是否相等，不能記錄大小關系，因為?ai%p>aj%p不代表ai>aj。

散列函數

散列函數是這樣一種特殊的函數。待處理的數據作為參數輸入給散列函數，散列函數對數據進行特定的處理之后，將對應生成的新數據返回出來。一般來說，使用散列和散列函數，是為了將不便于存儲、范圍過大的數據”壓縮成“便于存儲和使用的數據，之前所說的對質數取模就源于這種思想。

我們可以構造這樣一種散列函數對字符串進行壓縮：

f(s)=s[1]+s[2]+s[3]...+s[|s|]f(s)=s[1]+s[2]+s[3]...+s[|s|]

其中?s[i]表示字符串第i位的字符的ASCII?碼。

可以很明顯的看出來，散列函數往往有著共通的缺陷，即兩個不同的原數據可能會對應著相同的散列函數值。這時我們稱散列函數發生了沖突。

在算法競賽中，我們通常使用哈希（即散列）對字符串進行壓縮，將字符串壓縮成數字，從而方便、快速的比較兩個字符串。

通常情況下，我們對字符串進行壓縮時，會使用下面這種散列函數：

hash(s)=(s[1]×seed|s|?1+s[2]×seed|s|?2+...s[|s|]×seed0)%mod

其中?seed,mod分別為我們自行確定的兩個常數，一般情況下，mod要求是一個較大的質數。

這樣我們就把一個字符串轉化為了[0,mod]中的一個整數。

在比較兩個字符串是否相等時，我們就不必依次比較其對應位置的字符是否相等，而是直接比較兩個字符串的散列函數值是否相等。

那么，如何方便快捷的計算一個字符串s的子串s[l,r的散列函數值呢？

我們仔細觀察給出的散列函數的計算方式，會發現實際上我們就是把字符串s當作了一個seed進制數，每一位的字符對應的ASCII碼就是這個seed進制數在這一位上的數字。

所以要快速的取出子串的散列函數值，我們可以先計算出s的每個前綴的散列函數值。

即算：

hash[i]=hash(pre(s,i))=(s[1]×(seedi?1)+s[2]×(seedi?2)+...s[i]×(seed0))%mod

對于子串s[l,r]，其散列函數值等于：

(hash[r]?hash[l]?seedr?l+1)%mod

不過，在實際計算時，?(hash[r]?hash[l]?seedr?l+1)%mod可能會被計算成負數，此時我們要對其加上mod，從而轉化為[0,mod?1]?中的數。

上面公式中seed的取值通常為大于字符集的質數。

例如，對于字符串ababc，a,b,c對應的?ASCI碼分別為?97,98,99。

它的前綴?a,ab,aba,abab,ababc就分別對應著：

hash[1],hash[2],hash[3],hash[4],hash[5]hash[0]=0，seed=137,mod=10007hash[1]=(hash[0]?137+97)%mod=97hash[2]=(hash[1]?137+98)%mod=3380hash[3]=(hash[2]?137+97)%mod=2835hash[4]=(hash[3]?137+98)%mod=8227hash[5]=(hash[4]?137+99)%mod=6416

子串aba的hash值就等于：

(hash[3]?hash[0]?seed3)%mod=2835

子串abc的hash值就等于：

(hash[5]?hash[2]?seed3)%mod=2837

可以發現區間[1,2]和區間[3,4]?的字符串相同，其hash?值分別為：

(hash[2]?hash[0]?seed2)%mod=3380,(hash[4]?hash[2]?seed2)%mod=3380

hash值相同。

最小表示

我們有時會遇到這樣一類問題，比如判斷環形的數組是否相等，例如一串珠子圍成一個環，珠子編號分別為：?3,4,5,1,2?。

這串珠子是可以任意旋轉的，如果以4為第一個，我們看到的珠子編號就是4,5,1,2,3，如果以?11?作為第一個，那么編號為1,2,3,4,5。

給出一堆珠子的編號，讓我們判斷其中是否有一對珠子，可以通過旋轉，讓編號完全相等的。

對于珠串，?(1,2,3,4,5),(3,4,5,1,2)在數學上稱為同構。對于這類同構的問題，我們可以用最小表示法來判斷兩個珠串是否相同。

所謂最小表示法，套用之前的?Hash?散列函數，我們把?(1,2,3,4,5)?通過旋轉得到的5個串的?Hash值都算出來，但只用其中最小的那個值作為這個珠串的Hash?值。

(1,2,3,4,5),(2,3,4,5,1),(3,4,5,1,2),(4,5,1,2,3),(5,1,2,3,4)

利用我們上面提供的散列函數，如果已經計算出1,2,3,4,5)的Hash值，那么可以O(1)計算(2,3,4,5,1)的Hash值。即：

Hash(2,3,4,5,1)=((Hash(1,2,3,4,5)?1×seed5)×seed+′1′)%mod

計算所有n個Hash值所需的時間為O(n)。

鏈式Hash

之前提到，散列（Hash）有一個明顯的缺陷，即兩個不同的數據散列（Hash）之后得到的散列值（hash值）相同。那么，當我們要進行比較和查詢時，如果只是利用其hash值進行比較和查詢，就會發生錯誤。

事實上，我們可以通過鏈表來解決這種沖突。

對于每一個hash值x，我們用一個鏈表（桶）來存儲hash值為x的數據。

這樣就可以避免之前提到的錯誤出現。

例如，當我們想要查詢我們是否存儲過一個數據時，可以先求出它的hash值（即散列函數值），然后在其hash值對應的鏈表（桶）中，查找是否存在這個數據即可。例如發現與當前hash?值相同的還有?55?個數據，此時再將其與這5個數據本身的值逐個進行比較，看是否相同，如果都不相同，則將當前數據直接加到末尾，這樣相同的hash值就有6個了。不過，我們沒必要自己實現這樣的操作。在?C++中，unordered_set和unordered_map就是用鏈式hash的原理實現的。他們可以實現在?O(1)O(1)?的時間復雜度內進行查詢、插入等操作，不過，相對于一般的set和map，他們的缺陷在于內部元素并非有序的。

Stl中的Hash

在C++中，有幾種特別的STL工具，是使用hash表實現的。unordered_set與unordered_map就是這樣兩種STL工具。

unordered_set

插入、刪除、查詢等函數都和?set沒有差別。

和setset一樣保證內部元素沒有重復。

不保證內部元素有序。

操作的平均復雜度為?O(1)O(1)?。

unordered_set<int> S;

unordered_set<int> ::iterator it;

int?main(){

????S.insert(10);

S.insert(5);

????S.insert(7);

????S.insert(9);

????S.insert(5);

????S.insert(10);

????S.erase(5);

????for?(it = S.begin(); it != S.end(); it++)

????{

????????printf("%d ", *it);

???}

}

unordered_map

1. 賦值、查詢等操作都與?mapmap?沒有差別。
2. 不保證內部元素有序。操作的平均復雜度均為?O(1)O(1)?。

unordered_map<string, int> f;

int?main(){

????f["apple"] = 666;

????cout?<< f["apple"] << endl;

????f["catch"] = 919;

????cout?<< f["catch"] << endl;

????f.clear();

????cout?<< f["apple"] << " "?<< f["catch"] << endl;

}

非比較排序

在之前介紹過的快速排序和歸并排序，都是以比較為基礎操作的排序算法。這類算法的理論最優復雜度往往為O(nlogn)O(nlog?n)或O(n2)。

不過，本節中我們將介紹兩種特殊的排序算法，是不基于比較操作的排序算法，被稱為非比較排序。他們的最好時間復雜度甚至可以低至O(n)。

非比較排序的基本思路是，直接按照數值將數字放在應該放的位置，保證位置靠前的對應的數值更小，這樣就完成了從小到大的排序。

基數排序

算法描述

基數排序的基本思想是，先將待排序的所有數統一成相同的長度（位數不足的在前面補0）。

從最低位到最高位，按對應位的數字大小進行排序。在算法進行到第i位前，能夠保證序列是按最低的i?1位上的數排好序的。這樣當我們處理完每一位之后，所有數字就按其大小順序排好序了。因為每一位上的數字只有0?>9，我們可以先把該位為0的數字放在前面，再接下來放該位為1的數字...... 這樣就不用進行比較操作了。再進一步，如果所有數字都小于232。我們可以將它們看作是216（即65536）進制數。這些216進制數，最多只有兩位數，且每一位上的數字小于216。因此我們只要進行兩次排序操作，即先按低位排序，再按高位排序。每次排序時，按類似十進制的操作，先把對應位為0的數字放在前面，接下來放對應位為1的數字......最后放對應位為?65535?的數字。

這樣總的操作次數僅為?max(n,217)。

算法實現

具體的算法流程如下：

1. 計算出序列中每個數在216進制下的低位和高位數字分別是多少。
2. 依次按低位和高位數字進行排序，排序時，依次放對應位為0,1,...,65535的數字。

3. #define N 200020
   #define pii pair<int,int>
   using namespace std;
   int n, a[N], tot;
   pii p[N];
   vector<pii>G[N];
   int main()
   {cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];p[i].first = a[i] >> 16, p[i].second = a[i] % 65536;}for (int i = 1; i <= n; i++)G[p[i].second].push_back(p[i]);for (int i = 0; i < 65536; i++)for (int j = 0; j < G[i].size(); j++)p[++tot] = G[i][j];for (int i = 0; i < 65536; i++)G[i].clear();for (int i = 1; i <= n; i++)G[p[i].first].push_back(p[i]);tot = 0;	for (int i = 0; i < 65536; i++)for (int j = 0; j < G[i].size(); j++)p[++tot] = G[i][j];for (int i = 1; i <= n; i++)cout << ((p[i].first << 16) | p[i].second) << " ";
   }