子序列問題

對于序列 \(a(n)\)，我們稱 \(b(m)\) 為 \(a\) 的子序列，當且僅當存在 \(c(m)\) 使得 \(\forall 1\le i<m,c_i< c_{i + 1}\) 并且 \(\forall 1\le i \le m, a_{c_i} = b_i\)。

一個序列的子序列有 \(2^n\) 種，非空子序列有 \(2^n - 1\) 種。

子序列的子序列有 \(3^n\)​ 種，子序列的子序列的子序列有 \(4^n\) 種，依次類推。

[Ynoi2015] 盼君勿忘

每次詢問一個序列所有子序列去重後的權值和之和。

考慮對每個權值算貢獻，即有多少個子序列包含這個權值，簡單容斥下就是 \(2^n-2^{cnt}\) 個，是以貢獻就是 \((2^n-2^{cnt})x\)。

例題

給定一個子序列，求有多少個本質不同子序列。

定義 \(f_i\)​ 表示以 \(i\)​ 結尾的本質不同子序列數，顯然有 \(f_i = \sum f_j\)​，其中 \(s_j\)​ 是在 \(i\)​ 前面第一次出現。直接轉移可以做到 \(\mathcal{O}(|S|\sum)\)​。

事實上我們有更優的容斥方法，定義狀态 \(f_i\) 表示前 \(i\) 個位置有多少個本質不同的子序列數。

考慮從 \(f_i \to f_{i + 1}\)，顯然第 \(i + 1\) 位可選可不選，是以 \(f_{i + 1} = 2\times f_i - f_{pre_{i+ 1} - 1}\)，其中 \(pre_i\) 表示 \(i\) 前面第一個和 \(S_i\) 相同的位置。時間複雜度為 \(\mathcal{O}(|S|)\)。

【模闆】子序列自動機

子序列自動機相對于子序列，好比字尾自動機相對與字元串，回文自動機相對與回文串。

我們觀察例題的兩種方法，找到二者的本質相同之處。

不難發現如果我們對于所有 \(i<j\) 使得 \(s_j\) 是在 \(i\) 之後第一次出現，連一條 \(i\to j\) 的邊，那麼我們就會得到一個有向無環圖，即子序列自動機。

是以自動機中的一條路徑與一個子序列一一對應，本質不同的子序列數就是路徑數。

對于例題的第一種方法，\(f_i\)​​ 表示以 \(i\) 為終點了路徑數，對于第二種方法表示前 \(i\) 個點的路徑數，這樣就很清晰是正确的。

例2 Distinct Subsequences

求所有子序列的本質不同子序列個數之和。

顯然就是求所有子序列的子序列自動機中路徑條數。