奧義
多項式乘法，時間複雜度O(N²)，可以降為O(NlogN)。
取巧方式：多項式多點求值、函數值乘法、多項式內插。
多項式多點求值，x值是特殊數值：N次單位根的倒數，形成傅立葉轉換。多項式內插，則形成逆向傅立葉轉換。
傅立葉轉換擁有高速演算法，時間複雜度O(NlogN)。
數列函數轉換【尚無正式名稱，也許是generating function】
一、數列＝多項式。
(a₀ a₁ a₂) ←—→ a₀x⁰ + a₁x¹ + a₂x²
二、數列加法＝多項式加法。
(a₀ a₁ a₂) + (b₀ b₁ b₂) = (a₀+b₀ a₁+b₁ a₂+b₂)
a₀ x⁰ + a₁ x¹ + a₂ x²
+) b₀ x⁰ + b₁ x¹ + b₂ x²
—————————————————————————————————————————
(a₀+b₀) x⁰ + (a₁+b₁) x¹ + (a₂+b₂) x²
三、數列卷積＝多項式乘法。
(a₀ a₁ a₂) ∗ (b₀ b₁ b₂) = (c₀ c₁ c₂ c₃ c₄)
c₀ = a₀b₀
c₁ = a₀b₁ + a₁b₀
c₂ = a₀b₂ + a₁b₁ + a₂b₀
c₃ = a₁b₂ + a₂b₁
c₄ = a₂b₂
a₀ x⁰ + a₁ x¹ + a₂ x²
×) b₀ x⁰ + b₁ x¹ + b₂ x²
——————————————————————————————————————————————————
a₀b₂ x² + a₁b₂ x³ + a₂b₂ x⁴
a₀b₁ x¹ + a₁b₁ x² + a₂b₁ x³
a₀b₀ x⁰ + a₁b₀ x¹ + a₂b₀ x²
——————————————————————————————————————————————————
c₀ x⁰ + c₁ x¹ + c₂ x² + c₃ x³ + c₄ x⁴
四、數列循環卷積＝多項式循環乘法。（當xⁿ循環）
(a₀ a₁ a₂) ⊛ (b₀ b₁ b₂) = (c₀ c₁ c₂)
c₀ = a₁b₂ + a₂b₁ + a₀b₀
c₁ = a₂b₂ + a₀b₁ + a₁b₀
c₂ = a₀b₂ + a₁b₁ + a₂b₀
a₀ x⁰ + a₁ x¹ + a₂ x²
⊗) b₀ x⁰ + b₁ x¹ + b₂ x²
—————————————————————————————————————————————————————
a₀b₂ x² + a₁b₂ x³ + a₂b₂ x⁴
a₀b₁ x¹ + a₁b₁ x² + a₂b₁ x³
a₀b₀ x⁰ + a₁b₀ x¹ + a₂b₀ x²
—————————————————————————————————————————————————————
a₁b₂ x⁰ + a₂b₂ x¹ + a₀b₂ x² (when x³ = x⁰, x⁴ = x¹, ...)
a₂b₁ x⁰ + a₀b₁ x¹ + a₁b₁ x²
a₀b₀ x⁰ + a₁b₀ x¹ + a₂b₀ x²
—————————————————————————————————————————————————————
c₀ x⁰ + c₁ x¹ + c₂ x²
係值轉換【尚無正式名稱，也許是evaluation isomorphism】
一、N-1次多項式，N個係數變成N個函數值。
冪級數恰是多項式函數。藉由多項式內插，N個函數值可以還原成N個係數。請見本站文件「polynomial interpolation」。
a₀x⁰ + a₁x¹ + a₂x²
(a₀ a₁ a₂) <——————————————————> (y₀ y₁ y₂)
(x₀ x₁ x₂)
二、係數加法＝多項式加法＝函數值加法。
a₀x⁰ + a₁x¹ + a₂x²
(a₀ a₁ a₂) <——————————————————> (p₀ p₁ p₂)
+ b₀x⁰ + b₁x¹ + b₂x² +
(b₀ b₁ b₂) <——————————————————> (q₀ q₁ q₂)
‖ c₀x⁰ + c₁x¹ + c₂x² ‖
(c₀ c₁ c₂) <——————————————————> (r₀ r₁ r₂)
(x₀ x₁ x₂)
三、係數卷積＝多項式乘法＝函數值乘法。
a₀x⁰ + a₁x¹ + a₂x²
(a₀ a₁ a₂) <————————————————————————————————> (p₀ p₁ p₂)
∗ b₀x⁰ + b₁x¹ + b₂x² ×
(b₀ b₁ b₂) <————————————————————————————————> (q₀ q₁ q₂)
‖ c₀x⁰ + c₁x¹ + c₂x² + c₃x³ + c₄x⁴ ‖
(c₀ c₁ c₂ c₃ c₄) <————————————————————————————————> (r₀ r₁ r₂)
(x₀ x₁ x₂)
四、係數循環卷積＝多項式循環乘法＝函數值乘法。（當xⁿ循環）
a₀x⁰ + a₁x¹ + a₂x²
(a₀ a₁ a₂) <——————————————————> (p₀ p₁ p₂)
⊛ b₀x⁰ + b₁x¹ + b₂x² ×
(b₀ b₁ b₂) <——————————————————> (q₀ q₁ q₂) (when x³ = x⁰, x⁴ = x¹, ...)
‖ c₀x⁰ + c₁x¹ + c₂x² ‖
(c₀ c₁ c₂) <——————————————————> (r₀ r₁ r₂)
(x₀ x₁ x₂)
係值轉換（矩陣觀點）【尚無正式名稱】
一、係值轉換視作線性函數、寫作矩陣。
A = [ x⁰ x¹ x² ] transform
⎡ a₀ ⎤
a = ⎢ a₁ ⎥ coefficients
⎣ a₂ ⎦
⎡ a₀ ⎤
Aa = [ x⁰ x¹ x² ] ⎢ a₁ ⎥ = a₀x⁰ + a₁x¹ + a₂x² function value
⎣ a₂ ⎦
二、輸入加法＝輸出加法。
A = [ x⁰ x¹ x² ]
⎡ a₀ ⎤ ⎡ b₀ ⎤
a = ⎢ a₁ ⎥ b = ⎢ b₁ ⎥
⎣ a₂ ⎦ ⎣ b₂ ⎦
A(a + b) = (Aa) + (Ab)
三、輸入卷積＝輸出乘法。（尺寸不符，需要補項。）
à = [ x⁰ x¹ x² | x³ x⁴ ]
⎡ a₀ ⎤ ⎡ b₀ ⎤ ⎡ c₀ ⎤
ã = ⎢ a₁ ⎥ b̃ = ⎢ b₁ ⎥ c̃ = ⎢ c₁ ⎥
⎢ a₂ ⎥ ⎢ b₂ ⎥ ⎢ c₂ ⎥
⎢————⎥ ⎢————⎥ ⎢————⎥
⎢ 0 ⎥ ⎢ 0 ⎥ ⎢ c₃ ⎥
⎣ 0 ⎦ ⎣ 0 ⎦ ⎣ c₄ ⎦
Ã(ã ∗ b̃) = (Ãã) × (Ãb̃)
四、輸入循環卷積＝輸出乘法。
A = [ x⁰ x¹ x² ]
⎡ a₀ ⎤ ⎡ b₀ ⎤
a = ⎢ a₁ ⎥ b = ⎢ b₁ ⎥
⎣ a₂ ⎦ ⎣ b₂ ⎦
A(a ⊛ b) = (Aa) × (Ab)
指數一齊添上任意倍率，運算性質仍成立。
元素一齊添上任意倍率，運算性質仍成立。
一個橫條併成多個橫條，運算性質仍成立。
A = [ x⁰ x¹ x² ]
A = [ x⁰ x⁵ x¹⁰ ]
A = [ x⁰ x⁻⁷ x⁻²¹ ]
A = [ x⁰ x⁰ x⁰ ]
A = [ x⁰ x¹ x² ]
A = [ 7x⁰ 7x¹ 7x² ]
A = [ -x⁰ -x⁵ -x¹⁰ ]
A = [ 0 0 0 ]
⎡ 7x⁰ 7x¹ 7x² ⎤
A = ⎢ -x⁰ -x⁵ -x¹⁰ ⎥
⎢ x⁰ x⁻⁷ x⁻²¹ ⎥
⎣ x⁰ x⁰ x⁰ ⎦
對偶係值轉換（矩陣觀點）【尚無正式名稱】
接下來繼續補強矩陣，既滿足「輸入循環卷積＝輸出乘法」，也滿足「輸入乘法＝輸出循環卷積」，形成對偶運算。
從數學來看，補強性質，達成了對稱之美。從計算學來看，追加限制，產生了特殊演算法。
令原矩陣A、反矩陣A⁻¹，同時具備運算性質。一種嘗試是正規正交矩陣A⁻¹ = Aᵀ。
實數系統，xⁿ漸增，數值漸增，無法正規正交。失敗！
⎡ x⁰ x⁰ x⁰ x⁰ .. ⎤
⎢ x⁰ x¹ x² x³ .. ⎥
A = A⁻¹ = Aᵀ = ⎢ x⁰ x² x⁴ x⁶ .. ⎥ ✘
⎢ x⁰ x³ x⁶ x⁹ .. ⎥
⎣ : : : : ⎦
進一步嘗試封閉循環：令xⁿ循環。
一、複數系統傅立葉轉換：令x是N次單位根（的倒數）。
二、餘數系統數論轉換：令x是N階單位根（的倒數）。
Fourier transform: x = e-𝑖(2π/N), Nth root of unity
number theoretic transform: x = root of unity with order N
⎡ x⁰ x⁰ x⁰ x⁰ .. ⎤ ⎡ x⁻⁰ x⁻⁰ x⁻⁰ x⁻⁰ .. ⎤
⎢ x⁰ x¹ x² x³ .. ⎥ 1 ⎢ x⁻⁰ x⁻¹ x⁻² x⁻³ .. ⎥
A = ⎢ x⁰ x² x⁴ x⁶ .. ⎥ A⁻¹ = ——— ⎢ x⁻⁰ x⁻² x⁻⁴ x⁻⁶ .. ⎥
⎢ x⁰ x³ x⁶ x⁹ .. ⎥ N ⎢ x⁻⁰ x⁻³ x⁻⁶ x⁻⁹ .. ⎥
⎣ : : : : ⎦ ⎣ : : : : ⎦
總結：傅立葉轉換
數列、函數，互相轉換！
正向轉換：頭腦體操O(1)。
反向轉換：頭腦體操O(1)。
(a₀ a₁ a₂) ←—→ a₀x⁰ + a₁x¹ + a₂x²
係數、函數值，互相轉換！
正向轉換：多項式求值N回合O(N²)。
反向轉換：多項式內插O(N³)。
a₀x⁰ + a₁x¹ + a₂x²
(a₀ a₁ a₂) <——————————————————> (y₀ y₁ y₂)
(x₀ x₁ x₂)
矩陣觀點。Vandermonde matrix。
正向轉換：矩陣求值O(N²)。
反向轉換：矩陣求解O(N³)。
⎡ x₀⁰ x₀¹ x₀² ⎤ ⎡ a₀ ⎤ ⎡ y₀ ⎤
⎢ x₁⁰ x₁¹ x₁² ⎥ ⎢ a₁ ⎥ = ⎢ y₁ ⎥
⎣ x₂⁰ x₂¹ x₂² ⎦ ⎣ a₂ ⎦ ⎣ y₂ ⎦
高速演算法：複數系統傅立葉轉換、餘數系統數論轉換。
令矩陣共軛對稱、令矩陣正規正交、令xᵢ是單位根的每種次方、令矩陣邊長是2的次方。
正向轉換：O(NlogN)。
反向轉換：O(NlogN)。
⎡ x₀⁰ x₀¹ x₀² x₀³ ⎤ ⎡ a₀ ⎤ ⎡ y₀ ⎤
⎢ x₁⁰ x₁¹ x₁² x₁³ ⎥ ⎢ a₁ ⎥ = ⎢ y₁ ⎥
⎢ x₂⁰ x₂¹ x₂² x₂³ ⎥ ⎢ a₂ ⎥ ⎢ y₂ ⎥
⎣ x₃⁰ x₃¹ x₃² x₃³ ⎦ ⎣ a₃ ⎦ ⎣ y₃ ⎦
x = (ω⁰ ω¹ ... ωᴺ⁻¹)
ω = root of unity with order N
總結：循環卷積
係值轉換：係數循環卷積＝函數值乘法。
傅立葉轉換：係數循環卷積＝函數值乘法。係數乘法＝函數值循環卷積。
循環卷積演算法：係數循環卷積＝正向傅立葉轉換＆函數值乘法＆逆向傅立葉轉換。
circular convolution演算法
polynomial circular multiplication演算法
數列循環卷積的高速演算法：O(NlogN)！
正向傅立葉轉換O(NlogN)，對應項相乘O(N)，逆向傅立葉轉換O(NlogN)。總時間複雜度O(NlogN)。
傅立葉轉換的弱點是記憶體變兩倍（複數）、浮點數誤差。數論轉換的弱點是數值只能是整數、大於等於零、小於模數。
數列長度必須是2的次方。當數列長度不是2的次方，千萬不能直接補零到2的次方。
循環卷積計算結果：
(a₀ a₁ a₂) ⊛ (b₀ b₁ b₂) = (c₀ c₁ c₂)
c₀ = a₀b₀ + a₁b₂ + a₂b₁
c₁ = a₀b₁ + a₁b₀ + a₂b₂
c₂ = a₀b₂ + a₁b₁ + a₂b₀
補零直到長度是2的次方，計算結果完全不對：
(a₀ a₁ a₂ 0) ⊛ (b₀ b₁ b₂ 0) = (d₀ d₁ d₂ d₃)
d₀ = a₀b₀ + a₂b₂
d₁ = a₀b₁ + a₁b₀
d₂ = a₀b₂ + a₁b₁ + a₂b₀
d₃ = a₁b₂ + a₂b₁
正確方式：先補零直到不受循環影響，再補零直到長度是2的次方，最後讓輸出數列循環。
想要計算
(a₀ a₁ a₂) ⊛ (b₀ b₁ b₂) = (c₀ c₁ c₂)
先補零直到不受循環影響
(a₀ a₁ a₂ 0 0) ⊛ (b₀ b₁ b₂ 0 0) = (d₀ d₁ d₂ d₃ d₄)
再補零直到長度是2的次方
(a₀ a₁ a₂ 0 0 0 0 0) ⊛ (b₀ b₁ b₂ 0 0 0 0 0) = (d₀ d₁ d₂ d₃ d₄ 0 0 0)
最後讓輸出數列循環
c₀ = d₀ + d₃
c₁ = d₁ + d₄
c₂ = d₂
convolution演算法
polynomial multiplication演算法
運用循環卷積，計算卷積。總時間複雜度O(NlogN)。
想要計算
(a₀ a₁ a₂ a₃) ∗ (b₀ b₁ b₂) = (c₀ c₁ c₂ c₃ c₄ c₅)
先補零直到不受循環影響
(a₀ a₁ a₂ a₃ 0 0) ⊛ (b₀ b₁ b₂ 0 0 0) = (c₀ c₁ c₂ c₃ c₄ c₅)
再補零直到長度是2的次方
(a₀ a₁ a₂ a₃ 0 0 0 0) ⊛ (b₀ b₁ b₂ 0 0 0 0 0) = (c₀ c₁ c₂ c₃ c₄ c₅ 0 0)
截斷輸出數列至正確長度
(c₀ c₁ c₂ c₃ c₄ c₅ 0 0) → (c₀ c₁ c₂ c₃ c₄ c₅)
這個說法有點拗口。比較簡單的說法：兩個多項式相乘，則度數相加。為了讓多項式內插能夠得到正解，點數必須等於度數相加。多項式預先補零、追加度數、補足點數。
範例：大數乘法
大數乘法即是多項式乘法！
數論轉換、傅立葉轉換得以計算大數乘法，時間複雜度從O(N²)降為O(NlogN)。
範例：兩兩和（Minkowski sum）（X+Y problem）
甲集合、乙集合，只有整數。甲取一個數，乙取一個數，相加，會是哪些數？
集合資料結構是循序儲存：窮舉。O(N²)。
集合資料結構是索引儲存：卷積。O(RlogR)。R為數字範圍。
多項式觀點：整數是指數，該整數出現與否（未出現0，出現>0）是係數，兩兩和是多項式乘法。
卷積觀點：整數是索引值，相加是移位，兩兩和是卷積。
範例：組合計數（combination counting）
蓮霧2顆、椪柑3顆、芭樂5顆。欲在盤中擺放6顆水果，有幾種方式？
(x⁰+x¹+x²)(x⁰+x¹+x²+x³)(x⁰+x¹+x²+x³+x⁴+x⁵)，找到x⁶的係數。加是或、乘是且、次方是數量、係數是方式。如同兩兩和。
範例：數列搜尋（sequence searching）
經典問題「一條陣列，尋找一個值」，解法是循序搜尋、排序之後再二元搜尋。
進階問題「一條陣列，尋找一串連續數列」，解法是字串搜尋、卷積。此處討論卷積。
兩串數列 a b
a = (1 2 3 4)
b = (1 3 5 7)
定義兩串數列 a b 的差距：對應項的差的平方的總和。
(1 - 1)² + (2 - 3)² + (3 - 5)² + (4 - 7)²
定義兩串數列 a b 的差距：對應項的差的平方的總和。
sum (a[i] - b[i])²
當差距等於零，則兩串數列相同。
sum (a[i] - b[i])² = 0 ---> a = b
展開之後，重新整理，以數列為主角：數列每項平方和、數列點積。
sum (a[i] - b[i])²
= sum (a[i]² + b[i]² - 2 a[i] b[i])
= sum a[i]² + sum b[i]² - 2 sum a[i] b[i]
縮寫。
(a - b)² = a² + b² - 2 (a ∙ b)
兩串數列
(1 2 3 4 5 6)
(3 4 5)
窮舉各種對齊方式，判斷是否相符。
(1 2 3 4 5 6) (1 2 3 4 5 6) (1 2 3 4 5 6) (1 2 3 4 5 6)
| | | | | | | | | | | |
(3 4 5) (3 4 5) (3 4 5) (3 4 5)
換句話說，判斷差距是否等於零。
(a - b)² a² b² 2(a∙b)
(1-3)² + (2-4)² + (3-5)² = 1²+2²+3² + 3²+4²+5² - 2×26 = 12
(2-3)² + (3-4)² + (4-5)² = 2²+3²+4² + 3²+4²+5² - 2×38 = 3
(3-3)² + (4-4)² + (5-5)² = 3²+4²+5² + 3²+4²+5² - 2×50 = 0 <--- here!
(4-3)² + (5-4)² + (6-5)² = 4²+5²+6² + 3²+4²+5² - 2×62 = 5
^^^^^^^^ ^^
sliding window convolution
預先計算每個數字的平方、預先計算各種對齊方式的點積（就是卷積），就可以快速求得a² + b² - 2ab。時間複雜度O(NlogN)。
搜尋（找到零）、最相似（找最小值）、最相異（找最大值）。
UVa 12298 ICPC 4671 5705 7159
