#30370: 解題想法


r1cky (tour1st)

School : No School
ID : 158637
IP address : [223.137.191.195]
Last Login :
2023-01-30 11:11:33
i212. 三則運算 -- 小學三年級數學習作 | From: [1.34.88.173] | Post Date : 2022-05-16 21:51

大數加法:用陣列,記得進位,$\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}$的質數可能要找比較麻煩。

 

 

 
#30371: Re: 解題想法


linlincaleb@gmail.com (臨末之頌)

School : 新北市立板橋高級中學
ID : 132772
IP address : [203.64.161.129]
Last Login :
2022-10-28 15:50:09
i212. 三則運算 -- 小學三年級數學習作 | From: [111.248.107.73] | Post Date : 2022-05-16 23:02

大數加法:用陣列,記得進位,$\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,差點忘了

 
#30434: Re: 解題想法


fire5386 (Penguin07)

School : 國立清華大學
ID : 115822
IP address : [1.160.167.109]
Last Login :
2023-01-31 20:30:08
i212. 三則運算 -- 小學三年級數學習作 | From: [114.25.62.218] | Post Date : 2022-05-21 13:59

 

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


還有Orange的linlincaleb你也忘了

 
#31790: Re: 解題想法


a302854888@gmail.com (小麥)

School : No School
ID : 190267
IP address : [203.204.115.46]
Last Login :
2022-08-23 18:46:16
i212. 三則運算 -- 小學三年級數學習作 | From: [203.204.115.46] | Post Date : 2022-08-19 20:54

 

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


還有Orange的linlincaleb你也忘了


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

 
ZeroJudge Forum