什麼是DP？

推薦看一下。

正文

捲動陣列優化

在一些空間賊小，時間還好的 DP 題目裡，會用到優化空間的小技♂巧——捲動陣列優化。

捲動陣列，顧名思義，一個會捲動的陣列，主要是怎樣個滾法呢？接下來我先舉一個例子：

e.g

最長公共子序列（LCS）

給出兩個整數序列，求這兩個序列的†最長公共子序列。
†最長公共子序列：多個序列的共有的最長子序列。

這道題我們不難發現：
我們設 \(f_{i,j}\) 為從 \(1\) 到 \(i\) 的 \(a\) 子序列和從 \(1\) 到 \(j\) 的 \(b\) 子序列的 \(LCS\)。
它的狀態轉移方程即為

我們發現，狀態 \(f_{i,j}\) 只依賴於 \(f_{i-1,\dots}\) 和 \(f_{i,\dots}\)，那麼既然 \(i-2\) 及以後的狀態都沒用了，那麼我們可以把那之前的狀態給滾掉，即把第一維套上個 \(\% 2\)，思考一下，這裡十分的巧妙。

因為 \(mod\) 常數很大，我們為了優化常數，可以使用位運算，即 \(i\% 2\rightarrow i\&1\)，\((i-1)\% 2\rightarrow (i\oplus1)\&1\)

這樣我們將巨大的 \(O(n^2)\) 的空間壓縮到了 \(O(n)\)。

費用提前計算

在一些題目裡，它狀態的每一次轉移都會產生後效性，所以用普通的DP是做不了的，那麼，我們如何解決這個問題呢？

這時，我們有一種策略，就是既然我已經知道未來會被現在影響，那麼為什麼我不先把將要影響的算了呢？這，就是費用提前計算。

e.g

Luogu 2365 任務安排
題目描述
\(n\) 個任務排成一個序列在一臺機器上等待完成（順序不得改變），這 \(n\) 個任務被分成若干批，每批包含相鄰的若干任務。
從零時刻開始，這些任務被分批加工，第 \(i\) 個任務單獨完成所需的時間為 \(t_i\)。在每批任務開始前，機器需要啟動時間 \(s\)，而完成這批任務所需的時間是各個任務需要時間的總和（同一批任務將在同一時刻完成）。
每個任務的費用是它的完成時刻乘以一個費用係數 \(f_i\)。請確定一個分組方案，使得總費用最小。
對於 \(100\%\) 的資料，\(1\le n \le 5000\)，\(0 \le s \le 50\)，\(1\le t_i,f_i \le 100\)。

我們先設 \(dp_i\) 為前 \(i\) 天的答案，\(time_i\) 為前 \(i\) 天完成後的時間，經過手玩樣例過後發現狀態轉移方程為：

對於 \(time_j\)，我們可以表示為：

※ \(num\) 為前 \(i\) 天做的次數。

怎麼處理 \(num\) 呢？考慮到在每次做任務時，都會使當前和以後計算的時間加上 \(s\)，先不管轉移方程，我們現在對未來的影響為：

於是我們可以列出一個船新的狀態轉移方程：

因為我們在過去已經計算了影響現在的值，所以我們只需要計算 \(\sum^i_{k=1}t_k\)。以上的各種 \(\sum\) 均可以用字首和優化為 \(O(1)\) 的，所以時間複雜度為 \(O(n^2)\)。

數位DP

數位DP主要解決的是有關每個數位上的數位的一些關係，這種DP比較容易辨認，大多是一眼題，形如：

求 \(l\) 到 \(r(1\le l,r\le 10^{18})\) 中滿足以下性質的數的個數：

每個數位.........

我們可以使用類似字首和的思想，設 \(dp(i)\) 為 \(1\) 到 \(i\) 一共滿足性質的數的個數，答案即為 \(dp(r) - dp(l-1)\)。

發現可以對於一個已經固定最高位了的任意滿足條件的 \(k\) 位數的數量進行預處理，但是這個做法會假掉，原因：先設原數等於 \(\overline{kabcd\cdots e}\)（\(x\) 位數），則我們在處理滿足性質的最高位為 \(k\) 的 \(x\) 位數的個數可能會包含超出原數範圍的數，但是這部分的數是不可取的，並且難以維護 \(\overline{kabcd\cdots e}\) 以內的滿足性質的最高位為 \(k\) 的 \(x\) 位數的個數，所以做法假了。

注意到最高位小於 \(k\) 時，我們是可以使用上文預處理的方法的，於是我們可以分類討論：

列出以上樹形圖

對於左邊的分支，我們可以直接用先前預處理出來的值來更新 \(ans\)，對於右邊的分支，繼續往下走，記錄一下前面數位的情況，再針對前面的數位來進行下一位的轉移。

e.g.

AcWing 1081度的數量
求給定區間 \([X,Y]\) 中滿足下列條件的整數個數：這個數恰好等於 \(K\) 個互不相等的 \(B\) 的整數次冪之和。
例如，設 \(X=15,Y=20,K=2,B=2\)，則有且僅有下列三個數滿足題意：
\(17=2^4+2^0\quad 18=2^4+2^1\quad 20=2^4+2^2\)

簡化題意

求 \(X\) 到 \(Y\) 中滿足在 \(B\) 進位制下是一個 \(01\) 串的數的個數。

思路

我們將