大數加法:用陣列，記得進位，$\text{time complexity}$ : $O(N)$，這裡我們假設$N$代表數字總位數。
大數減法:用注意借位問題，$\text{time complexity}$ :$O(N)$。
應該可以注意到上面的其實和普通手算的方式差不多，只是用電腦算比較大的數字而已
但乘法，如果用普通的直式乘法呢，我們考慮$A \times B$，一個$A$的位數乘上$B$的所有位數，有$N$個為$O(N)$，但是$A$有$N$位，$O(N) \times N = O(N^2)$，會$\color{blue}{TLE}$
我們把兩個數表示成多項式，答案即是乘起來後進位，這裡普通的多項式乘法$\text{time complexity}$還是$O(N^2)$，但我們可以利用$\text{FFT}$或$\text{NTT}$來以$O(NlogN)$求得，這樣就會$\color{green}{AC}$
補充:
一、$\text{FFT}$ : 快速傅立葉轉換，利用複數平面的特殊性質計算，是$\text{DFT}$(離散傅立葉轉換)的加速版，對於$N$項的倆多項式相乘為$O(NlogN)$的，不過注意他是用$\text{double}$計算，有可能卡精度或卡常
卡常解決方式:
(1) 遞迴改成非遞迴，$\text{FFT}$前把他底層順序排好，可以加速很多
(2) 宣告$\text{const/final}$等修飾詞，會加速一些，據某個姓謝的說這可能是$\color{blue}{TLE}$的最後一根稻草。
(3) 用$\text{NTT}$，$\text{NTT}$不用$\text{double}$計算。
二、$\text{NTT}$ : 數論轉換，和$\text{FFT}$概念類似，但把複數概念以原根與$\text{mod}$代替，可以避免$\text{double}$噴出來的常數以及誤差，缺點是這題的$\text{time limit}$，我在解這題的時候因為有部分測資數字較小，而他給時限也比較小，但$\text{NTT}$有點難自由變動，原根與$\text{mod}$的質數可能要找比較麻煩。
linlincaleb@gmail.com
(臨末之頌)
學校
:
新北市立板橋高級中學
編號 : 132772
來源 : [203.64.161.123]
最後登入時間 ：
2024-07-29 10:02:49
大數加法:用陣列，記得進位，$\text{time complexity}$ : $O(N)$，這裡我們假設$N$代表數字總位數。
大數減法:用注意借位問題，$\text{time complexity}$ :$O(N)$。
應該可以注意到上面的其實和普通手算的方式差不多，只是用電腦算比較大的數字而已
但乘法，如果用普通的直式乘法呢，我們考慮$A \times B$，一個$A$的位數乘上$B$的所有位數，有$N$個為$O(N)$，但是$A$有$N$位，$O(N) \times N = O(N^2)$，會$\color{blue}{TLE}$
我們把兩個數表示成多項式，答案即是乘起來後進位，這裡普通的多項式乘法$\text{time complexity}$還是$O(N^2)$，但我們可以利用$\text{FFT}$或$\text{NTT}$來以$O(NlogN)$求得，這樣就會$\color{green}{AC}$
補充:
一、$\text{FFT}$ : 快速傅立葉轉換，利用複數平面的特殊性質計算，是$\text{DFT}$(離散傅立葉轉換)的加速版，對於$N$項的倆多項式相乘為$O(NlogN)$的，不過注意他是用$\text{double}$計算，有可能卡精度或卡常
卡常解決方式:
(1) 遞迴改成非遞迴，$\text{FFT}$前把他底層順序排好，可以加速很多
(2) 宣告$\text{const/final}$等修飾詞，會加速一些，據某個姓謝的說這可能是$\color{blue}{TLE}$的最後一根稻草。
(3) 用$\text{NTT}$，$\text{NTT}$不用$\text{double}$計算。
二、$\text{NTT}$ : 數論轉換，和$\text{FFT}$概念類似，但把複數概念以原根與$\text{mod}$代替，可以避免$\text{double}$噴出來的常數以及誤差，缺點是這題的$\text{time limit}$，我在解這題的時候因為有部分測資數字較小，而他給時限也比較小，但$\text{NTT}$有點難自由變動，原根與$\text{mod}$的質數可能要找比較麻煩。
你們這些毒瘤大師 對 我說的就是你 becaido 還有老鼠(還是企鵝(?)) 喔對 還有STSTONE，差點忘了