[ gcc Built-in Functions for binary ] gcc內建處理二進位函數

以下介紹的函數都是非標準的函數，他只能在GCC底下使用，不過一般的比賽環境都是支援的，所以熟記起來可以增加寫位元運算的效率

1. int __builtin_ffs (unsigned int x)
   int __builtin_ffsl (unsigned long)
   int __builtin_ffsll (unsigned long long)
   
   • 返回右起第一個1的位置
   • Returns one plus the index of the least significant 1-bit of x, or if x is zero, returns zero.
2. int __builtin_clz (unsigned int x)
   int __builtin_clzl (unsigned long)
   int __builtin_clzll (unsigned long long)
   
   • 返回左起第一個1之前0的個數
   • Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.
    
3. int __builtin_ctz (unsigned int x)
   int __builtin_ctzl (unsigned long)
   int __builtin_ctzll (unsigned long long)
   
   • 返回右起第一個1之後的0的個數
   • Returns the number of trailing 0-bits in x, starting at the least significant bit position. If x is 0, the result is undefined.
    
4. int __builtin_popcount (unsigned int x)
   int __builtin_popcountl (unsigned long)
   int __builtin_popcountll (unsigned long long)
   
   • 返回1的個數
   • Returns the number of 1-bits in x.
    
5. int __builtin_parity (unsigned int x)
   int __builtin_parityl (unsigned long)
   int __builtin_parityll (unsigned long long)
   
   • 返回1的個數的奇偶性(1的個數 mod 2的值)
   •  Returns the parity of x, i.e. the number of 1-bits in x modulo 2. 

這種內建函數其實非常多，這邊有附上一個GCC內建函數的列表，有興趣的朋友可以參考
https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html

當你在GCC環境下，想直接用01寫二進位的東西，其實有簡單的方法:

• cout<<0b1010101;
• cout<<0b1010101LL;

這樣你的編譯器應該會警告你說這是GCC內建的東西(C++14以後的版本會支援它)，但是還是會正確執行，都是85，個人覺得蠻方便的

如果你是用C++11，可以用stoi,stol,stoll,stoul,stoull等函數來把二進位字串轉成int,long,long long,unsigned long,unsigned long long等，可以設定他用二進位轉換，像是這樣:

• cout<<stoi("1010101",NULL,2);
• cout<<stoll("1010101",NULL,2);

 另外有些編譯器會在<algorithm>實作std::__lg(n)這個函數，他會回傳$\floor{log_2n}$的值，可以參考這個
http://stackoverflow.com/questions/40434664/what-is-std-lg

[ Amortized analysis - Potential method ] 平攤分析 - 勢能方法

對於一個stack操作，pop和push都是$\ord{1}$的，這很好理解，現在定義了一個新的操作，pop_all，表示pop stack內的所有元素，顯然這是一個$\ord{N}$的操作。那我們進行一連串的push、pop、pop_all的複雜度上界是多少呢？

根據big-O的特性，因為pop_all是$\ord{N}$的，我們把每個操作都當作$\ord{N}$來看，執行$N$次操作的總複雜度就會是$\ord{N^2}$。這沒有錯，但怎麼想都覺得怪怪的，怎麼可能一直執行pop_all呢？執行一次pop_all之後stack就沒有元素了耶！

這三種操作不是平行的，而是互相影響的。換言之，你每次的push創造“機會”給pop和pop_all。pop和pop_all才能“消費”著這些機會，不存在無限制的消費。

因此這個複雜度是高估的，那要究竟怎麼真正去計算$N$次操作的總複雜度呢？

勢能方法

對於一個資料結構$DS$，我們定義$\Phi(DS)$表示$DS$的“勢能”，而且要保證在任何情況下$\Phi(DS) \geq 0$。

通常$\Phi(DS)$我們會定義他是$DS$的某個性質，像是元素個數啦，如果是二元樹的話可能是所有節點左子樹大小減右子樹大小的絕對值的總和啊、或是葉節點的個數啊...各種東西都可以當作是$DS$的勢能。

 那$\Phi(DS)$能用來幹甚麼？我們定義$\Phi_0$表示$DS$在還沒有進行任何操作時的勢能，假設有$N$個操作，第$i$個操作的時間花費為$t_i$，這個操作結束之後的勢能為$\Phi_i$，$i>0$，我們定義第$i$個操作的均攤時間$a_i=t_i+C(\Phi_i-\Phi_{i-1})$，這裡$C>0$是一個常數

可以發現總均攤花費時間：
$$
\sum^{N}_{i=1}a_i=\sum^{N}_{i=1}(t_i+C(\Phi_i-\Phi_{i-1})) \\
=(t_1+t_2+...+t_n)+C(-\Phi_0+(\Phi_1-\Phi_1)+(\Phi_2-\Phi_2)+...+(\Phi_{n-1}-\Phi_{n-1})+\Phi_n) \\
=\sum^{N}_{i=1} t_i +C(\Phi_N-\Phi_0)
$$
最後得到：
$$
\sum^{N}_{i=1}t_i=\sum^{N}_{i=1}a_i-C(\Phi_N-\Phi_0)
$$
這個特性告訴我們，只要好好選擇$\Phi(DS)$函數，就可以在$\ord{\sum^{N}_{i=1}t_i}$很難直接求的情況下透過$\ord{\sum^{N}_{i=1}a_i-C(\Phi_N-\Phi_0)}$求出$\ord{\sum^{N}_{i=1}t_i}$。

證明範例

有了勢能方法，可以很輕鬆的用它來計算一些資料結構操作的均攤複雜度。

以剛剛stack的例子來說，我們設定stack $S$它的勢能函數$\Phi(S)$為$S$的元素個數，可以確定$\Phi_0=0$且$\Phi(S) \geq 0$。

我們設一次的push、一次的pop花費一單位的時間，並設常數$C=1$，在第$i$次操作：

• 如果是push操作的話$t_i=1$，stack的元素個數增加$1$
  因此$\Phi_i-\Phi_{i-1}=1$
  $a_i=t_i+\Phi_i-\Phi_{i-1}=1+1=2$
• 如果是pop操作的話$t_i=1$，stack的元素個數減少$1$
  因此$\Phi_i-\Phi_{i-1}=-1$
  $a_i=t_i+\Phi_i-\Phi_{i-1}=1-1=0$
•  如果是pop_all操作的話$t_i=n$，stack的元素個數減少$n$
  因此$\Phi_i-\Phi_{i-1}=-n$
  $a_i=t_i+\Phi_i-\Phi_{i-1}=n-n=0$

$a_i$的最大值是$2$，經過$N$次操作之後$\Phi_N-\Phi_0$的最小值為$0$
可以知道：
$$
\ord{\sum^{N}_{i=0}t_i}=\ord{\sum^{N}_{i=1}a_i-(\Phi_N-\Phi_0)}=\ord{2N+0}=\ord{N}
$$
因此經過$N$次stack的任何有效操作之後，總花費的時間為$\ord{N}$，這才是我們滿意的結果。

對了，通常來說$\Phi_0$都會是0，因此在大部分的情況下：
$$
\ord{\sum^{N}_{i=0}t_i}=\ord{\sum^{N}_{i=1}a_i}
$$
所以大部分的證明都會忽略掉$\Phi_N-\Phi_0$的部分

[ Minimum Arborescence / zhu_liu ] 朱劉算法 - 最小樹形圖

在有向圖中，給定一個點$r$作為生成樹的根，找出有向圖最小生成樹。

首先我們要能保證從$r$能夠走到圖上的所有點，這樣生成樹才會存在，這很簡單，一次DFS即可，再來是把圖上的所有自環移除，因為一顆樹裡面很明顯是不會有自環的。

之後就是算法的主要步驟了，可以先想一下，除了$r$以外的每一個點都有一條儘可能小的邊指向自己，最好的情況就是我們枚舉每一個點（除了根節點）並找到最小的一條指向這個點的邊，如果這些邊不構成有向環，就形成了一個所求的最小樹形圖。

但是實際上會出現環啊，但是這些環一定是獨立的，為甚麼呢？因為只有$|V|-1$條邊啊，只有是一棵樹的時候才會是連通的狀態。換句話說，如果圖連通了，就一定是最小樹形圖。

我們嘗試去換一些邊，使圖連通，在換的過程中我們總是選擇較小的邊，那麼得到的就是最小樹形圖。你可能會去枚舉一些邊把有向環拆掉，但是這樣的話可能會產生新的有向環，不是一個好做法。

朱劉算法就不直接去換邊，它也不去拆掉環，而是在不增加邊的情況下讓圖連通，怎麼做呢？就是用一個新的點代替原來圖的一個環（也就是所謂的「縮點」，和強連通分量有點像），並且修改跟這個環裡的點有關的邊的權值。

為何要修改邊的權重呢？當我們每更換一個點的入邊的時候我們就要去掉原來那個入邊，於是我們把這個點所有可能的入邊全部減少原來選取的那個入邊的權值，這樣每增加一條入邊無形中就刪去了原來那條邊。

上圖中紅色部分是要進行縮點的有向環

每個環上的點所有可能的入邊全部減少原來選取的那個入邊的權值

接著把環縮成一個點就可以了

假設我們想要把原來縮環之前3那條邊換成4那條邊，那我們換完的結果如下:

可以發現修改邊權後，不需要把邊刪掉，直接去計算選取邊的權重和就會和換邊的結果一樣

朱劉算法主算法的過程就是：找最小入邊->判斷有沒有環(沒有環就退出，算法成功)->縮點，改權值，如此反覆，一般來說為了方便不會去記錄縮點後虛擬節點裡包含了那些點，如果需要找出最小樹形圖包含的邊，就必須要真的去記錄他。

時間複雜度來說的話，用當時論文提出的實作方式，修改邊權的部分為$\ord{|E|}$，縮點最多執行$|V|-1$次，所以總複雜度是$\ord{|V|*|E|}$。
我自己有想了一個$\ord{|E| \; log \; |E|}$的方法，需要用到一種可以合併和把裡面所有元素加上某個值 的heap，又因為每個點最多只會連出去$|V|-1$條邊，也就是heap裡面只有$|V|$個元素是有用的，所以可以在heap大小為$2|V|$時把後$|V|$個元素刪掉，用斐式堆可以做到$\ord{|E|+|V| \; log|V|}$。

以下為$\ord{|V|*|E|}$的code:
接著是$\ord{|E| \; log^2|E|}$的code，使用啟發式合併(感謝59491、編譯器幫忙debug):
接著是$\ord{|E| \; log|E|}$的code，使用skew heap:

[ 0-1 Fractional Programming Dinkelbach algorithm ] 0-1分數規劃

【定義】

給你兩個數組，$benefit[i]$表示選$i$的利潤、$cost[i]$表示選$i$的花費。
如果選$i$，定義$x[i]=1$否則$x[i]=0$，通常題目會給你選擇的限制條件，像是必須是一顆生成樹之類的，這裡就把它忽略掉
我們的目標是要求$\frac{\sum{benefit[i] \times x[i]}}{\sum{cost[i] \times x[i]}}$的最大值。

【分析】

先不管最大化問題，令$\frac{\sum{benefit[i] \times x[i]}}{\sum{cost[i] \times x[i]}}=L$
可以把式子改寫成$(\sum{benefit[i] \times x[i]})-L \times (\sum{cost[i] \times x[i]})=0$
分離參數得到$\sum{(benefit[i]-L \times  cost[i]) \times x[i]}=0$
只要知道$L$，$(benefit[i]-L \times  cost[i])$是直接可以求出來的，先記他為$d(i,L)$吧
那可以設$f(L)=\sum{d(i,L) \times x[i]}$

我們的目標變成是要最大化$L$
那若存在一種$x$的選法使得$f(L)>0$能夠證明什麼呢?
$f(L)>0 \to \frac{\sum{benefit[i] \times x[i]}}{\sum{cost[i] \times x[i]}}>L$那表示存在另一個$L$會比現在的$L$還要好
那 $f(L)<0$?很明顯這種情況完全沒有意義，因為找不到這種$L$

最佳的$L$會讓所有$x$的選法都$f(L)\leq0$，只要找到這樣的$L$就說明他是最佳解了
也可以用類似的想法求最小化$L$，這裡就不贅述了。

【解法】

根據剛剛找出來的性質$f(L)$是單調性的，我們可以二分搜$L$，然後驗證是否存在一組解使得$f(L)>0$，這很簡單就不附code了。
另一個有效率的算法是Dinkelbach，他跟二分搜不一樣的地方是他要去求解，在驗證解跟求解的複雜度一樣的時候Dinkelbach是會比較快的，但有時候求解的複雜度會比驗證解的複雜度還要高，因此要看情況使用
以下附上虛擬碼：

常見的題型有：最優比率環、最優比率生成樹、最大密度子圖(有flow解)等

[ dominator tree ] 有向圖的支配樹

dominator tree，中文名稱叫支配樹
給一張有向圖$G$，我們從其中一個點$r$出發到$y$的所有路徑中，一定會經過點$x$，就稱$x$是$y$的必經點；我們把距離$y$最近的必經點稱為最近必經點，記為$idom(y)$。
支配樹上的有向邊$(u,v)$滿足$idom(v)=u$，那對於一個點$y$，$y$的所有必經點就會是支配樹上$r$到$y$路徑上的所有點。
這個東西可以求有向圖的割點、橋(在每個邊加入虛擬點)等等。
注意code裡的$idom$跟我定義的不一樣
我是看這份講義的偽代碼寫出來的：

[ Pi algorithms - John Machin's formula ] 梅欽公式計算圓周率

我們知道
$$\frac{\pi}{4}= \arctan 1$$
而$\arctan(x)$的泰勒展開式長這樣
$$\arctan(x)=x-\frac{x^3}{3}+\frac{x^5}{5}-\frac{x^7}{7}+\frac{x^9}{9}- \cdots \; (x \leq 1)$$
故可以求出莱布尼茨公式如下:
$$\frac{\pi}{4}= 1 \,-\, \frac{1}{3} \,+\, \frac{1}{5} \,-\, \frac{1}{7} \,+\, \frac{1}{9} \,-\, \cdots$$
但是這用來計算$\pi$到小數點後指定位數是非常困難的，因此有了以下的梅欽公式:
$$\frac{\pi}{4} = 4 \arctan \frac{1}{5} - \arctan \frac{1}{239}$$
再用泰勒展開，可以得到:
$$\pi=(\frac{16}{5} - \frac{16} {3*5^3} + \frac{16}{5 * 5^5} - \frac{16} {7 * 5^7} + \cdots) \\ - (\frac{4}{239} - \frac{4}{3 * 239^3} + \frac{4}{5 * 239^5} - \frac{4}{7 * 239^7} + \cdots)$$
可以將這個公式整理為:
$$\pi=\frac{\frac{16}{5} - \frac{4}{239}}{1} -\frac{\frac{16}{5^3} - \frac{4}{239^3}}{3} + \frac{\frac{16}{5^5} - \frac{4}{239^5}}{5} - \cdots$$
如果我們要計算圓周率至10的負$L$次方，由於$\frac{16}{5^{2*n-1}} - \frac{4}{239^{2*n-1}}$中$\frac{16}{5^{2*n-1}}$比$\frac{4}{239^{2*n-1}}$來的大，具有決定性，所以表示至少必須計算至第n項:
$$\frac{16}{(2*n-1)*5^{2*n-1}}=10^{-L}$$
將上面的等式取log並經過化簡，我們可以求得(誤差什麼得先不管它):
$$n =\frac{L}{2log_{10} 5} = \frac{L}{1.39794}$$
這樣就可以計算$\pi$到小數點後第$L$位了

這裡有其他可以快速算出圓周率的梅欽類公式
http://jeux-et-mathematiques.davalan.org/calc/formulespi.pdf

[ Earley parser ] Earley語法解析器

有一天蚯蚓跟我說CYK算法很慢，推薦了這個東西，所以我就把他寫出來了。
他主要是先建構出類似於自動機的圖，有很多個狀態在跳來跳去，在我的實作裡有將其轉成語法樹的方法。
這裡需要自己實作的有lexer，還有最後的語法一定要有一個gamma rule，gamma rule就是有一個$gamma \Longrightarrow S$，$S$是初始符號。
首先是語法規則的部分:

這是分析器的本體，lexer的部分要自己去完成，lexer的結果會是parse的第二個參數，計算出來一些資料會存在table裡面
以下為模板:

最後是構造語法樹的部分，因為div是一顆左兄弟右兒子的樹，所以要將她轉換成正常的語法樹，還要去記錄曖昧文法的部分: