Sequence

「數列」。一串數字。

(4 -1 6 0 9)

我們習慣用一維陣列儲存一個數列：

int a[5] = {4, -1, 6, 0, 9};

以下介紹一些經典的數列運算。

加減乘除

對應項加減乘除。

加法 (1 2 3) + (4 5 6) = (1+4 2+5 3+6) = (5 7 9)

累和、差分

前項累加、鄰項相減。

累和 ∑ (4 -1 6 0 9) = (4 3 9 9 18)
差分　 Δ (4 -1 6 0 9) = (4 -5 7 -6 9)

最小值、最大值、總和

靜態版本請見本站文件「Maximum Sum Subarray」。

動態版本請見本站文件「Sequence」。

最小值 min (4 -1 6 0 9) = -1
最大值 max (4 -1 6 0 9) = 9
總和　 ∑ (4 -1 6 0 9) = 18

排序、搜尋、選擇、計數

請見本站文件「Sort」。

排序 (4 -1 6 0 9) → (-1 0 4 6 9)
搜尋 (4 -1 6 0 9) , 0 → 3
選擇 (4 -1 6 0 9) , 0 → -1
計數 (4 -1 6 0 9) , 0 → 1

數列搜尋

請見本站文件「String Searching」。

數列搜尋 (4 -1 6 0 9) , (0 9) → 3

排列、組合

請見本站文件「Permutation」。

排列 (4 -1 6 0 9) → (6 0 9 -1 4)
組合 (4 -1 6 0 9) → (-1 0 9)

點積、卷積

請見本站文件「Convolution」。

點積 (1 2 3) · (4 5 6) = 1×4 + 2×5 + 3×6 = 32
卷積 (1 2 3 4 5) ∗ (4 5 6) = (4 13 28 43 58 49 30)

(- - 1 2 3 4 5 - -) · (6 5 4 - - - - - -) = 4
(- - 1 2 3 4 5 - -) · (- 6 5 4 - - - - -) = 13
(- - 1 2 3 4 5 - -) · (- - 6 5 4 - - - -) = 28
(- - 1 2 3 4 5 - -) · (- - - 6 5 4 - - -) = 43
(- - 1 2 3 4 5 - -) · (- - - - 6 5 4 - -) = 58
(- - 1 2 3 4 5 - -) · (- - - - - 6 5 4 -) = 49
(- - 1 2 3 4 5 - -) · (- - - - - - 6 5 4) = 30

On-Line Encyclopedia of Integer Sequences

自古以來，數學家研發了許多特殊數列，數量成千上萬。事實上已經有熱心人士，建立百科全書：「整數數列線上大全OEIS」。每當遇到陌生數列，可以在網站上尋找參考文獻。

Sequence運算

    result (noun)
--- --------------------------
+   direct sum     直和（加法）
×   direct product 直積（乘法）
·   dot product    點積
∗   convolution    卷積

註：芒星asterisk、角星star是不同東西。
　　芒星*(U+002A)、角星★(U+2605)
　　芒星運算子∗(U+2217)、角星運算子⋆(U+22C6)
　　卷積運算符號是六芒星，最理想的字元是芒星運算子∗(U+2217)。
　　根據字型選擇，芒星運算子可能顯示五芒星、六芒星、八芒星。

加減乘除

對應項加減乘除。

(a₀ a₁ a₂) + (b₀ b₁ b₂) = (a₀+b₀ a₁+b₁ a₂+b₂)

int a[3] = {1, 2, 3}; int b[3] = {4, 5, 6}; int c[3]; void add() { for (int i=0; i<3; ++i) c[i] = a[i] + b[i]; }

點積

對應項相乘，通通加總。

(a₀ a₁ a₂) ∙ (b₀ b₁ b₂) = a₀b₀ + a₁b₁ + a₂b₂

int a[3] = {1, 2, 3}; int b[3] = {4, 5, 6}; int dot() { int sum = 0; for (int i=0; i<3; ++i) sum += a[i] * b[i]; return sum; }

卷積

許多次點積。第二串數列頭尾顛倒（迎合多項式乘法）；窮舉各種對齊方式，各做一次點積（卷積的名稱由此而來）。

(a₀ a₁ a₂ a₃ a₄) ∗ (b₀ b₁ b₂) = (c₀ c₁ c₂ c₃ c₄ c₅ c₆)

c₀: (-  -  a₀ a₁ a₂ a₃ a₄ -  - )
    (b₂ b₁ b₀ -  -  -  -  -  - )

c₁: (-  -  a₀ a₁ a₂ a₃ a₄ -  - )
    (-  b₂ b₁ b₀ -  -  -  -  - )

c₂: (-  -  a₀ a₁ a₂ a₃ a₄ -  - )
    (-  -  b₂ b₁ b₀ -  -  -  - )

c₃: (-  -  a₀ a₁ a₂ a₃ a₄ -  - )
    (-  -  -  b₂ b₁ b₀ -  -  - )

c₄: (-  -  a₀ a₁ a₂ a₃ a₄ -  - )
    (-  -   -  - b₂ b₁ b₀ -  - )

c₅: (-  -  a₀ a₁ a₂ a₃ a₄ -  - )
    (-  -  -  -  -  b₂ b₁ b₀ - )

c₆: (-  -  a₀ a₁ a₂ a₃ a₄ -  - )
    (-  -   -  -  -  - b₂ b₁ b₀)

int a[5] = {1, 2, 3, 4, 5}; int b[3] = {4, 5, 6}; int c[5+3-1]; void convolution() { for (int i=0; i<5+3-1; ++i) { c[i] = 0; for (int j=0; j<3; ++j) if (i-j >= 0 && i-j < 5) c[i] += a[i-j] * b[j]; } }

循環卷積

超出數列的部分，改成頭尾循環。

(a₀ a₁ a₂ a₃ a₄) ⊛ (b₀ b₁ b₂ b₃ b₄) = (c₀ c₁ c₂ c₃ c₄)

c₀:               c₁:               c₂:
(a₀ a₁ a₂ a₃ a₄)  (a₀ a₁ a₂ a₃ a₄)  (a₀ a₁ a₂ a₃ a₄)
(b₀ b₄ b₃ b₂ b₁)  (b₁ b₀ b₄ b₃ b₂)  (b₂ b₁ b₀ b₄ b₃)

c₃:               c₄:
(a₀ a₁ a₂ a₃ a₄)  (a₀ a₁ a₂ a₃ a₄)
(b₃ b₂ b₁ b₀ b₄)  (b₄ b₃ b₂ b₁ b₀)

int a[5] = {1, 2, 3, 4, 5}; int b[5] = {5, 6, 7, 8, 9}; int c[5]; void circular_convolution() { for (int i=0; i<5; ++i) { c[i] = 0; for (int j=0; j<5; ++j) c[i] += a[(i-j+5)%5] * b[j]; } }

Sequence運算

    result (noun)
--- -------------------------------------------------
    cumulative sum    累積和　（前綴和）　（離散積分）
Δ   finite difference 有限差分（向前差分）（離散微分）　分什麼分

註：累積和運算符號，目前尚未定義。
註：有限差分運算符號，源自微積分的變化量符號Δ。注意到是Δy而不是Δx。
　　視為動作，應該是梯度∇。視為結果，才是變化量Δ。

Additive Integral（Cumulative Sum）（Summatory Function）

「加性積分」。至今每一項相加。O(N)。

(a₀ a₁ a₂ a₃ a₄) ---> (a₀ a₀+a₁ a₀+a₁+a₂ a₀+a₁+a₂+a₃ a₀+a₁+a₂+a₃+a₄)

數列 (4 -1  6  0  9)
累和 (4  3  9  9  18)

b(n) = sum a(i)
       i≤n

int a[5] = {4, -1, 6, 0, 9}; int sum[5]; // 累和 void cumulative_sum() { sum[0] = a[0]; for (int i=1; i<5; i++) sum[i] = sum[i-1] + a[i]; } // [i,j]區間和。 // 預先以O(N)計算累和，便能以O(1)計算區間和。 int interval_sum(int i, int j) { if (i > j) swap(i, j); if (i == 0) return sum[j]; return sum[j] - sum[i - 1]; } // 陣列開頭加一空格，就不必擔心超出陣列邊界。程式碼更簡潔。 int a[5+1] = {0, 4, -1, 6, 0, 9}; int sum[5+1] = {0}; // 累和 void cumulative_sum() { for (int i=1; i<=5; i++) sum[i] = sum[i-1] + a[i]; } int interval_sum(int i, int j) { if (i > j) swap(i, j); return sum[j] - sum[i - 1]; }

UVa 10324 10994 983

Additive Derivative（Finite Difference）

「加性微分」。相鄰數字差。O(N)。

累和與鄰差互為反運算！可以相互抵消！一個數列，先累和、再鄰差，仍是原數列。一個數列，先鄰差、再累和，仍是原數列。

數列 (4 -1  6  0  9)
鄰差 (4 -5  7 -6  9)

(a₀ a₁ a₂ a₃ a₄) ---> (a₀ a₁-a₀ a₂-a₁ a₃-a₂ a₄-a₃)

a(n) = b(n) - b(n-1)

int a[5] = {4, -1, 6, 0, 9}; int diff[5]; // 鄰差 void finite_difference() { diff[0] = a[0]; for (int i=1; i<5; i++) diff[i] = a[i] - a[i-1]; }

UVa 10038

Multiplicative Integral

「乘性積分」。因數項相加。O(NloglogN)。

(a₁ a₂ a₃ a₄ a₅) ---> (a₁ a₁+a₂ a₁+a₃ a₁+a₂+a₄ a₅)

b(n) = sum a(i)
       i|n

int a[5] = {4, -1, 6, 0, 9}; vector<int> prime; void multiplicative_integral() { for (int p: prime) for (int i=p; i<=n; i++) if (i % p == 0) a[i] += a[i / p]; } void multiplicative_integral() { for (int p: prime) for (int i=1; i<=n; i++) { if (i * p > n) break; a[i * p] += a[i]; } }

luogu P5495

Multiplicative Derivative

「乘性微分」。質因數排容。O(NloglogN)。

a(n) = sum b(i) μ(i;n)
       i|n

Subset Integral

「子集積分」。子集項總和。

b(n) = sum a(i)
       i⊆n

Subset Derivative

「子集微分」。

Poset Integral（Zeta Transform）

「偏序集積分」。

b(n) = sum a(i)
       i≤n

Poset Derivative（Möbius Transform）

「偏序集微分」。

a(n) = sum b(i) μ(i;n)
       i≤n

Additive Convolution（Cauchy Product）

「加性卷積」。配對運算是加法運算。

c(n) = sum a(i)b(j) = sum a(i)b(n-i) = sum a(n-i)b(i)
      i+j=n           i≤n              i≤n

當b數列全是1，即是加性積分。後面小節以此類推。

演算法是Fast Fourier Transform。O(NlogN)。

請見本站文件「Convolution」。

Multiplicative Convolution（Dirichlet Convolution）

「乘性卷積」。配對運算是乘法運算。

c(n) = sum a(i)b(j) = sum a(i)b(n/i) = sum a(n/i)b(i)
      i×j=n           i|n              i|n

目前沒有高速演算法。演算法是Divide and Conquer。計算一項的時間複雜度O(n^¾)。乘性函數降至O(n^⅔)。

請見本站文件「Convolution」。

Subset Convolution

「子集卷積」。配對運算是互斥聯集運算。

c(n) = sum a(i)b(j) = sum a(i)b(n\i) = sum a(n\i)b(i)
      i⊔j=n           i⊆n              i⊆n

Poset Convolution

「偏序集卷積」。配對運算是小於等於運算。

一個偏序集，子集合總和（偏序集積分）、子集合排容（偏序集微分），互為反運算。

積分前卷積 = 積分後乘法。定義祖性卷積：令兩元素的結合結果是最低共同祖先LCA。數列卷積的結合運算子是加法、乘法，偏序集卷積則是LCA。

fast zeta transform
https://mycourses.aalto.fi/mod/resource/view.php?id=90388

引入cyclic inclusion-exclusion就滿足對偶了？此時偏序集積分的效果等同於FFT、FNT等轉換。

Invitation to Algorithmic Uses of Inclusion–Exclusion
https://arxiv.org/abs/1105.2942

時間複雜度從O(Nᴺ)降到O(2ᴺN)。

Poset Convolution

當偏序集是子集關係。結合運算子是聯集。

當偏序集是分割數（組合數）關係，此定理即是巴斯卡三角形。

當偏序集是因數關係，此定理即是Möbius inversion。此時偏序集微積分可以寫成乘性卷積：積分是摺以常數函數1，微分是摺以Möbius function μ。結合運算子是最小公倍數。

    偏序集積分
    --------->
 祖 |        | 點
 性 |        | 乘
 摺 |        |        我猜是這樣
 積 v        v
    <---------
    偏序集微分
　  乘性卷積（因數關係）

Dyadic Convolution

「二元卷積」。配對運算是位元運算AND、OR、XOR。

希臘語dyadic、拉丁語binary，兩者同義。數學家喜歡dyadic，計算學家喜歡binary。

c(n) = sum a(i)b(j) = sum a(i)b(n∧i) = sum a(n∧i)b(j)   bitwise AND
      i∧j=n           i⊆n              i⊆n
c(n) = sum a(i)b(j) = sum a(i)b(n∨i) = sum a(n∨i)b(j)   bitwise OR
      i∨j=n           i⊆n              i⊆n
c(n) = sum a(i)b(j) = sum a(i)b(n⊕i) = sum a(n⊕i)b(j)   bitwise XOR
      i⊕j=n           i⊆n              i⊆n

二進位數字視作集合，AND、OR、XOR視作交集、聯集、聯集減交集。

演算法仿照Fast Walsh-Hadamard Transform。O(NlogN)。

https://taodaling.github.io/blog/2019/04/24/快速沃尔什变换/

// recursive // https://blog.csdn.net/liangzhaoyang1/article/details/52819835 void FWT( ll X[], int l, int r, int v ) { if ( l == r ) return; int m = ( l + r ) >> 1; FWT( X, l, m, v ); FWT( X, m + 1, r, v ); FOR ( i, 0, m - l ) X[ l + i ] += X[ m + 1 + i ] * v; } // iterative // https://www.cnblogs.com/HITLJR/p/7668136.html void FWT(int a[], int n) { for (int d=1; d<n; d<<=1) for (int m=d<<1, i=0; i<n; i+=m) for (int j=0; j<d; j++) { int x = a[i+j], y = a[i+j+d]; // xor a[i+j] = (x+y) % mod; a[i+j+d] = (x-y+mod) % mod; // and // a[i+j] = x+y; // or // a[i+j+d] = x+y; } } void solve(int a[], int b[], int n) { FWT(a, n); FWT(b, n); for (int i=0; i<n; i++) a[i] = a[i] * b[i] % mod; UFWT(a, n); }

luogu P4717

數列函數轉換【尚無正式名稱，也許是Generating Function】

離散數列、連續函數，互相轉換！

轉換方式，無限可能，自由發揮。

數學家並未命名轉換過程，只命名轉換結果：「生成函數」。

(2 -5  1  0  4)  ⟷  2x¹ - 5x¹ + 1x² + 0x³ + 4x⁵
 sequence a(n)         generating function f(x)

生成函數的其中一種經典形式是各項相加：「級數」。

一、冪級數：指數是索引值（從0開始）。

二、狄利克雷級數：底數是索引值（從1開始）。

(2 -5  1  0  4)  ⟷  2x⁰ - 5x¹ + 1x² + 0x³ + 4x⁴
                          power series

(2 -5  1  0  4)  ⟷  2⋅1ˣ - 5⋅2ˣ + 1⋅3ˣ + 0⋅4ˣ + 4⋅5ˣ
                          Dirichlet series

數列函數轉換的對應運算【尚無正式名稱】

離散數列運算、連續函數運算，互相對應。

對應運算，請見本站文件「Transformation」。

一、離散數列加法減法＝連續函數加法減法。

(2 -5  1)  ⟷  2x⁰ - 5x¹ + 1x²
    +                 +
(1 -1  0)  ⟷  1x⁰ - 1x¹ + 0x²
    ‖                 ‖
(3 -6  1)  ⟷  3x⁰ - 6x¹ + 1x²

二、離散數列乘法除法＝未定義。

(2 -5  1)  ⟷  2x⁰ - 5x¹ + 1x²
    ×          no such operator
(1 -1  0)  ⟷  1x⁰ - 1x¹ + 0x²
    ‖                 ‖
(2  5  0)  ⟷  2x⁰ + 5x¹ + 0x²

三、離散數列卷積反卷積＝連續函數乘法除法。

離散數列的卷積運算，源自於連續函數的乘法運算。數學家故意將兩者定義成一樣。

(2 -5  1)        ⟷  2x⁰ - 5x¹ + 1x²
    ∗                       ×
(1 -1  0)        ⟷  1x⁰ - 1x¹ + 0x²
    ‖                       ‖
(2 -7  7  1  0)  ⟷  2x⁰ - 7x¹ + 7x² + 1x³ + 0x⁴

四、未定義＝連續函數卷積反卷積。

(2 -5  1)        ⟷  2x⁰ - 5x¹ + 1x²
no such operator            ∗
(1 -1  0)        ⟷  1x⁰ - 1x¹ + 0x²
    ‖                       ‖
    ?            ⟷         ?

係值轉換【尚無正式名稱，也許是Evaluation Isomorphism】

係數、函數值，互相轉換！

需要事先決定：級數是哪種、x值是哪些。

            2x⁰ - 5x¹ + 1x²
(2 -5  1)  <———————————————>  (2 -4  8)
             x = {0, 2, 6}

級數視作線性函數、寫做矩陣。令反矩陣存在，以保證一對一轉換。令x值數量等同數列長度、令x皆相異，以保證反矩陣存在。

線性函數，請見本站文件「Linear Function」。

[ 0⁰ 0¹ 0² ] [  2 ]   [  2 ]
[ 2⁰ 2¹ 2² ] [ -5 ] = [ -4 ]
[ 6⁰ 6¹ 6² ] [  1 ]   [  8 ]

係值轉換的對應運算【尚無正式名稱】

一、係數加法減法＝函數加法減法＝函數值加法減法。

            2x⁰ - 5x¹ + 1x²
(2 -5  1)  <———————————————>  (2 -4  8)
    +                             +
            1x⁰ - 1x¹ + 0x²
(1 -1  0)  <———————————————>  (1 -1 -5)
    ‖                             ‖
            3x⁰ - 6x¹ + 1x²
(3 -6  1)  <———————————————>  (3 -5  3)
             x = {0, 2, 6} 

二、係數卷積反卷積＝函數乘法除法＝函數值乘法除法。

                        2x⁰ - 5x¹ + 1x²
(2 -5  1)        <———————————————————————————>  (2 -4  8)
    ∗                                               ×
                        1x⁰ - 1x¹ + 0x²
(1 -1  0)        <———————————————————————————>  (1 -1 -5)
    ‖                                               ‖
                  2x⁰ - 7x¹ + 7x² + 1x³ + 0x⁴
(2 -7  7  1  0)  <———————————————————————————>  (2  4 -40)
                         x = {0, 2, 6}

備忘

L'Hôpital's rule: a/b = a'/b'
https://en.wikipedia.org/wiki/L%27H%C3%B4pital%27s_rule

Lambert series: a/Δa = a∗*1 , a = Δa∗⁺1
https://en.wikipedia.org/wiki/Lambert_series

Perron's formula:
https://en.wikipedia.org/wiki/Perron%27s_formula
https://en.wikipedia.org/wiki/Abel%27s_summation_formula

Lagrange inversion theorem: a⁻¹()
https://en.wikipedia.org/wiki/Lagrange_inversion_theorem
https://en.wikipedia.org/wiki/Formal_power_series

Hasse-Teichmüller derivatives order k: aₙ xⁿ -> C(n,k) aₙ xⁿ⁻ᵏ
https://en.wikipedia.org/wiki/Hasse_derivative
https://en.wikipedia.org/wiki/Umbral_calculus

difference operator: (Δf)(n) = f(n+1) - f(n)
Δ(n³) = (n+1)³ - n³ = 3n² + 3n + 1

shift operator: E