[ Mersenne Twister ] 梅森旋轉算法

梅森旋轉算法是一種可以快速產生高級偽隨機數的算法，修正了很多以前的隨機速算法的缺陷(Ex:線性同於算法)。

這是專門用在蒙地卡羅測試用的，不要拿它來做持久化隨機二叉數的亂數產生器，會太慢

最為廣泛使用Mersenne Twister的一種變體是MT19937，可以產生32位整數序列，從C++11開始，C++也可以使用這種算法。在Boost C++,Glib和NAG數值庫中，作為插件提供。但是一般在競賽時可能會有不支援的情況發生，所以將它做成模板當作參考。

MT19937_64則是可以產生64位整數序列

以下提供模板:

[ chinese remainder theorem ] 中國剩餘定理

我是看維基百科實現的，所以就直接貼上模板
注意:

• crt函數的m[i]是模數
• crt函數的a[i]是原本數模m[i]後的值
• 必須要保證m兩兩互質
• 容易溢位

模板:

[ Number Theoretic Transform ] 快速數論變換)(NTT)

這也不知道怎麼說明，應該是我數學太爛的關係，直接看連結吧

• 維基百科-數論變換
• 多项式乘法运算终极版
• 从多项式乘法到快速傅里叶变换
• Morris的code

有以下幾點要注意:

1. P要是一個q*2^k+1的質數，G是P的原根
2. N(數列長度)要是2的冪次
3. (P-1)%N=0
4. 做了逆轉換後的結果為原本數列mod P的結果，所以P要夠大
5. 如果要求P是任意數的話，可以用中國剩餘定理處理

這裡有一些質數和它的原根(按質數順序由大到小排):

• 2615053605667*(2^18)+1,3
• 15*(2^27)+1,31
• 479*(2^21)+1,3
• 7*17*(2^23)+1,3
• 3*3*211*(2^19)+1,5
• 25*(2^22)+1,3

因為可能會有A*B%M的情況發生，所以需要用
long long 乘 long long 模 long long不溢位算法
只需要將code裡面所有的A*B%M的部分改掉即可

以下提供模板(bit_reverse參考自Morris):

[ fast fourier transform - Cooley Tukey ] 快速傅立葉轉換(FFT)

因為不知道怎麼說明所以提供一些網址:

• 多项式乘法运算初级版
• 从多项式乘法到快速傅里叶变换
• Morris的code 

注意:

• N(數列長度)要是2的冪次

以下提供模板(bit_reverse參考自Morris):