模擬對數空間的圖靈機

基本概述

問題一般分類為判定型，構造型，計數型 \(\dots\)

可以構造模擬對數空間的圖靈機。\(M(x,y)\)，其中 \(x\) 是輸入，\(y\) 是需要判定的東西。計數題就是判定有多少個 \(y\) 合法，或者是統計 \(y\) 的容斥系數。比如說我們在統計序列數量的時候，傳入的 \(y\) 就是需要被判定的序列，我們在自動機內部需要設計一個算法判定其是否合法。這個算法的空間復雜度如果 \(\le O(\log n)\)，就可以在多項式時間復雜度內解決。

只有在工作區的空間復雜度才計入復雜度，輸入和輸出的一些是不算的，數字是以二進制形式表示（所以你如果開一個值域為 \(V\) 的變量，那么就是 \(\log V\)）。外層 DP 的時候就要記錄內層狀態，假設內層狀態大小為 \(|s|\)，外層狀態的大小就是 \(2^{|s|}\)，所以只有在空間為 \(\log\) 級別的時候才能有多項式做法。

例子

非講課內容，但是我覺得 ARC074E 這題非常適合當作例子。

考慮傳入序列 \(y\)，我們如何判定其是否合法。掃描 \(y\)，變量 \(i\)，當前顏色位置在 \(i\)，另外兩個顏色位置在 \(j,k\)，通過這三個變量我們就可以快速判定是否符合區間。空間復雜度 3\log n。所以狀態數就是 \(2^{3\log n}=n^3\)。

通過判定方法，我們就可以很快知道了 dp 要記錄當前枚舉到了序列的第幾個位置，上一個不同的顏色的位置，以及上一個與這兩個顏色都不同的顏色位置。然后就解決了本題。

本質是用最小的狀態數記錄能刻畫當前 DP 目標的東西。 轉化為圖靈機能方便我們思考。

應用

AGC013D Piling Up

給定一個顏色序列，如何判定合法？轉化為走格子，遇到黑色向右上，遇到白色向右下。這個路徑要求 \(y\) 坐標極差不超過 \(n\)，記錄循環變量 \(i\)，坐標 \(y\) 和最大最小 \(y\)，這是 \(4\log n\) 的。但是其實只需要記錄當前點到最大最小 \(y\) 的距離就行了。這樣子是 \(3\log n\) 的空間，所以 dp 是 \(O(n^3)\) 的。

其實我們直接傳入 \(M(x,y,z)\)，多了一個 \(z\) 表示下界，注意到多個下界是同構的。于是就可以做到 \(O(n^2)\) 的了。

局限性

可以發現上述方法只能做一個按照線性順序的 dp，無法求解區間 dp，樹形 dp 之類的。可以用雙射拆分。

DP 優化