#29719: FFT


fire5386 (becaidorz)

學校 : 國立清華大學
編號 : 115822
來源 : [140.114.217.8]
最後登入時間 :
2024-04-13 22:06:23
h386. Apples and Bananas -- CSES2111 | From: [114.25.89.201] | 發表日期 : 2022-03-24 22:12

把A和B換成多項式的形式,其中次方代表重量,係數代表這個重量的數量

例如 A = [1, 2, 3], B = [2, 4]

$A(x) = (1x^1 + 1x^2 + 1x^3)$

$B(x) = (1x^2 + 1x^4)

$C(x) = A(x) * B(x) = 1x^3 + 1x^4 + 2x^5 + 1x^6 + 1x^7$

代表各個重量的組合數

$A(x) * B(x)$ 多項式乘法的部分可以用快速傅立葉變換(FFT)做到 $O(n * \log(n))$ 的時間複雜度

 
#29720: Re:FFT


fire5386 (becaidorz)

學校 : 國立清華大學
編號 : 115822
來源 : [140.114.217.8]
最後登入時間 :
2024-04-13 22:06:23
h386. Apples and Bananas -- CSES2111 | From: [114.25.89.201] | 發表日期 : 2022-03-24 22:13

$B(x) = (1x^2 + 1x^4)$

 
ZeroJudge Forum