大數加法:用陣列，記得進位，$\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)$，會$TLE$

我們把兩個數表示成多項式，答案即是乘起來後進位，這裡普通的多項式乘法$\text{time complexity}$還是$O(N^2)$，但我們可以利用$\text{FFT}$或$\text{NTT}$來以$O(NlogN)$求得，這樣就會$AC$

補充:

一、$\text{FFT}$ : 快速傅立葉轉換，利用複數平面的特殊性質計算，是$\text{DFT}$(離散傅立葉轉換)的加速版，對於$N$項的倆多項式相乘為$O(NlogN)$的，不過注意他是用$\text{double}$計算，有可能卡精度或卡常

卡常解決方式:

(1) 遞迴改成非遞迴，$\text{FFT}$前把他底層順序排好，可以加速很多

(2) 宣告$\text{const/final}$等修飾詞，會加速一些，據某個姓謝的說這可能是$TLE$的最後一根稻草。

(3) 用$\text{NTT}$，$\text{NTT}$不用$\text{double}$計算。

二、$\text{NTT}$ : 數論轉換，和$\text{FFT}$概念類似，但把複數概念以原根與$\text{mod}$代替，可以避免$\text{double}$噴出來的常數以及誤差，缺點是這題的$\text{time limit}$，我在解這題的時候因為有部分測資數字較小，而他給時限也比較小，但$\text{NTT}$有點難自由變動，原根與$\text{mod}$的質數可能要找比較麻煩。

大數加法:用陣列，記得進位，$\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)$，會$TLE$

我們把兩個數表示成多項式，答案即是乘起來後進位，這裡普通的多項式乘法$\text{time complexity}$還是$O(N^2)$，但我們可以利用$\text{FFT}$或$\text{NTT}$來以$O(NlogN)$求得，這樣就會$AC$

補充:

一、$\text{FFT}$ : 快速傅立葉轉換，利用複數平面的特殊性質計算，是$\text{DFT}$(離散傅立葉轉換)的加速版，對於$N$項的倆多項式相乘為$O(NlogN)$的，不過注意他是用$\text{double}$計算，有可能卡精度或卡常

卡常解決方式:

(1) 遞迴改成非遞迴，$\text{FFT}$前把他底層順序排好，可以加速很多

(2) 宣告$\text{const/final}$等修飾詞，會加速一些，據某個姓謝的說這可能是$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，差點忘了

 

你們這些毒瘤大師 對 我說的就是你 becaido 還有老鼠(還是企鵝(?)) 喔對 還有STSTONE，差點忘了

還有Orange的linlincaleb你也忘了

 

你們這些毒瘤大師 對 我說的就是你 becaido 還有老鼠(還是企鵝(?)) 喔對 還有STSTONE，差點忘了

還有Orange的linlincaleb你也忘了

老鼠真的好毒喔 FFT大師+NTT怪獸