0x10 數位dp簡介
數位dp通常用于解決這類題目：
給定一個範圍 \(l\) ~ \(r\) ，求出這個範圍内，符合某種條件的數字個數、數字的和或數字的積。
給出的數字非常之巨大，采用 \(O(N)\) 的算法無法通過題目，當我們遇到這類題目時，通常是拿不到暴力分的。
于是，我們在遇到這類題目時，通常要使用數位dp來解決。
0x20 數位dp實作方式
我們通常都使用記憶化搜尋的方法來進行實作，可以 \(AC\)。
注意，當我們的記憶化不當時，或搜尋次數、參量處理不當時，我們很有可能會逾時或得到錯誤的答案。
是以，設計好的參量和狀态，認真處理每個參量，是十分重要的。
這裡給出記憶化搜尋的模闆，一個好的模闆可以幫助你靈活面對難度較大的題目。
int tot = 0;//tot為數字的位數。
int dig[20];//dig為數字拆分後的各個位上的數字。
int dp[255][255];//dp為設計的轉移狀态。
int dfs (int now, int cnt, int zero, int limit) {
//now為目前的處理的位數。
//cnt為變量，用來存儲例如1的個數。數位累計和等。
//zero标記目前是否有前導零。
//limit為限制，也就是是否到達數字的邊界。
if (now > tot) {
return 1;
/*處理的位數已經超過了數字的個數，也就表示該數字處理完成，退出循環。
而通常傳回1，表示該數合法，因為之前的操作都是當處理位數合法的時候進行的。
當然，根據題目和寫法的不同，可能操作上有差異。
*/
}
if (!limit && !zero && dp[now][cnt] != -1) {
return dp[now][cnt];
//該操作就是記憶化的展現。
//對于有的題目，前導零可能對于答案沒有影響，是以需要靈活調整條件。
//而狀态初始為-1，當目前狀态不為-1時，也就是該狀态處理過了。
//而根據記憶化的操作，我們就可以直接傳回答案了。
}
int up = limit ? dig[tot - now + 1] : 9;
//up表示邊界，當目前數字已經是邊界了的時候，就是dig[tot-now+1].
//否則，該進制的最大數位數字，十進制就是9，二進制就是1。
int ans = 0;
//在大部分情況中，答案不止于int範圍，依舊需要根據情況理智處理。
for (int i = 0; i <= up; i ++) {//枚舉數字從0到up
if ()......//按情況寫條件
ans += dfs (now + 1, 目前狀态轉移, (zero && i == 0), (i == dig[now]));
//對于第三個參量，搜尋目前标記zero為真且枚舉目前數字為0時，zero标記才為真，否則為假。
//對于第四個參量，目前數字為目前搜尋的數字時，limit标記才為真，否則為假
}
if (!limit && !zero) {
dp[now][cnt] = ans;
//這裡是記憶化的存儲，條件依舊需要根據情況書寫。
}
return ans;
//傳回答案
}
0x30 數位dp基礎
在難度不是很高的情況下，記憶化搜尋就能幫助我們完成很多題目。既然我們了解了數位dp的概念和基本實作方法，那我們就用幾道基礎例題來快速提升自己吧！
0x31 基礎例題 \(1\)
P4317 花神的數論題
按照我們上面記憶化搜尋的模式，我們在搜尋時，需要設 \(4\) 個參數。但是我們在該題可以很直接的看出，前導零是不會對答案造成影響的，因為它并不會影響二進制下 \(1\) 的個數。是以，我們搜尋的時候，隻需要設立 \(3\) 個參量就可以了。
而dp數組的狀态對我們來說其實是不太重要的，我們隻要将其運用固定地用在記憶化的地方就可以了。
該題我們直接采用暴力累乘，并不用擔心時間，将模闆套用即可。
可能需要吸氧。
代碼講解如下：
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int mod = 10000007;
const int N = 115;
int dig[15], tot = 0;
ll dp[N][N];
ll dfs (int now, int cnt, int lim) {
//隻需要設立三個參數。
//cnt：二進制下1的個數。
if (now > tot) {
return cnt;
//當處理的位數超過數字的個數時，表示處理結束，傳回答案。
}
if (!lim && dp[now][cnt] != -1) {
return dp[now][cnt];
//滿足記憶化的要求。
}
ll res = 1;//因累乘，是以初始化為1。
int up = lim ? dig[tot - now + 1] : 1;//定義邊界。
for (int i = 0; i <= up; i ++) {
ll tp = dfs (now + 1, cnt + (i == 1), (lim && (i == up)));
//對于第二個參量，當目前數字為1時才增加答案。
//當邊界标記為真且目前數字為邊界時，邊界标記才為真。
res = max (1ll, tp) * res % mod;
//tp可能小于1，是以和1取max，直接暴力累乘。
}
if (!lim) {
dp[now][cnt] = res;
//記憶化的記錄答案。
}
return res;
}
ll calc (ll x) {
memset (dp, -1, sizeof (dp));
//狀态的初始值。
do {
dig[++tot] = x % 2;
x /= 2;
}while (x);
//二進制拆分。
return dfs (1, 0, 1);
//初始處理第1位，1的個數為0，邊界标記為真。
}
int main() {
ll n;
scanf ("%lld", &n);
printf ("%lld", calc (n));
return 0;
}
0x32 基礎例題 \(2\)
P2657 [SCOI2009] windy 數
由于需要判斷目前數字和上一個數字的差是否為 \(2\) ，是以要記錄上一位的數字。于是記憶化搜尋的變量設定為上一個數字。
在枚舉下一個數字時，如果不滿足相差為 \(2\) 的條件，那麼可以直接跳過。注意，如果目前有前導零，那麼該數位可以任意填。
根據字首和的思想，題目給出的 \(a\) 和 \(b\) 區間，我們計算出的是 \(1\) 到 \(a\) 和 \(1\) 到 \(b\) 滿足條件的數字個數。
于是我們需要輸出 \(1\) 到 \(b\) 滿足條件的數字個數減去 \(1\) 到 \(a-1\) 滿足條件的個數，就是我們最終的答案。
于是這樣，大體的思路就出來了，靈活運用模闆就可以通過。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
int dig[15], dp[115][115], tot = 0;
int dfs (int now, int last, int zero, int limit) {
if (now > tot) {
return 1;
//處理完了傳回該數合法
}
if (!limit && dp[now][last] != -1) {
return dp[now][last];
//記憶化
}
int sum = 0, up = limit ? dig[tot - now + 1] : 9;
//定義邊界
for (int i = 0; i <= up; i ++) {
if (i < last + 2 && i > last - 2 && !zero) {
continue;
//不符合相差為2的條件
}
sum += dfs (now + 1, i, (zero && !i), (limit && (i == up)));
//對于第三個參量，當枚舉的數位為0且目前為0時，前導零标記才為真。
//目前邊界标記為真且目前枚舉的數位到達邊界，邊界标記才為真。
}
if (!zero && !limit) {
dp[now][last] = sum;
//記憶化的記錄答案。
}
return sum;
}
ll calc (ll x) {
memset (dp, -1, sizeof (dp));
memset (dig, 0, sizeof (dig));
tot = 0;
//這裡的初始化很重要，不要忘記。
do {
dig[++tot] = x % 10;
x /= 10;
}while (x);
//十進制拆分。
return dfs (1, -1, 1, 1);
}
int main() {
ll a, b;
scanf ("%lld%lld", &a, &b);
printf ("%lld", calc (b) - calc (a - 1));
//字首和思想的運用。
return 0;
}
0x33 基礎例題 \(3\)
P4124 [CQOI2016]手機号碼
對于此題，我們的記憶化搜尋參量就不止 \(4\) 個了。
我們需要多增加 \(3\) 個參量：
\(1.\) 标記是否出現過 \(4\)。
\(2.\) 标記是否出現過 \(8\)。
\(3.\) 标記是否構成三連号。
另外，我們依舊有用到字首和的思想。但是當我們将左邊界減去一後，無法滿足電話号碼 \(11\) 位的條件，這裡我們需要特判。
我們依舊需要記憶化來優化時間，大體的代碼就能寫出來了。
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
int dig[15], tot = 0;
ll dp[35][15][15][3][3][3][3];
ll dfs (int pos, int now, int last, bool con3, bool f4, bool f8, bool limit) {
if (f4 == true && f8 == true) {
return 0;
//同時出現4和8時，退出搜尋。
}
if (pos == 0) {
return con3 == true ? 1 : 0;
//搜尋完時，判斷是否三連号，否則不合法。
}
if (!limit && dp[pos][now][last][con3][f4][f8][limit] != -1) {
return dp[pos][now][last][con3][f4][f8][limit];
//記憶化傳回答案。
}
int up = limit ? dig[pos] : 9;//邊界。
ll ans = 0;
for (int i = 0; i <= up; i ++) {
bool c3 = false;
if (last == i && i == now) {
c3 = true;
//三連号标記。
}
ans += dfs (pos - 1, i, now, (c3 || con3), (i == 4 || f4), (i == 8 || f8), limit && i == dig[pos]);
//對于第四個參量，隻要目前構成三連号并且三連号标記為真，接下去搜尋的三連号标記就為真。
//對于第五個參量，隻要目前有4或者标記4為真，接下去搜尋的4标記就為真。
//對于第六個參量，隻要目前有8或者标記8為真，接下去搜尋的8标記就為真。
//對于第七個參量，當邊界标記為真且目前數位到達邊界，邊界标記為真。
}
if (!limit) {
dp[pos][now][last][con3][f4][f8][limit] = ans;
//記憶化記錄答案。
}
return ans;
}
ll calc (ll x) {
tot = 0;
do {
dig[++tot] = x % 10;
x /= 10;
}while (x);
//拆分。
ll ans = 0;
for (int i = 1; i <= dig[tot]; i ++) {
ans += dfs (tot - 1, i, -1, false, (i == 4), (i == 8), (i == dig[tot]));
//累計答案。
}
return ans;
}
int main() {
ll l, r;
scanf ("%lld%lld", &l, &r);
memset (dp, -1, sizeof (dp));
if (l == 10000000000) {
printf ("%lld", calc (r));
return 0;
//特判。
}
printf ("%lld", calc(r) - calc (l - 1));
return 0;
}
0x40 數位dp進階
對于一些難度較高的題目，單憑記憶化搜尋的時間優化無法通過。
于是，我們需要對于狀态進行合并、預處理或剪枝等。這些進階的方法可以幫助我們實作時間上的巨大優化。
接下來，就從幾道進階的數位dp例題來學習優化時間的方法吧。
0x41 進階例題 \(1\)
P4127 [AHOI2009]同類分布
很明顯，如果按照之前的模闆操作，這道題是輕而易舉的。
但是，當我們記錄dp狀态的時候，就會發現情況不對。
這裡的數字會達到 \(10^{18}\) ，我們無法記錄 dp狀态了。
于是這裡，我們就很容易想到取模的做法。
那我們将什麼作為模數呢？
我們可以枚舉所有的數位之和來當做模數。
于是，判斷 \(mod\) 與數位上的和相同且原來的數字模數位上的和為 \(0\) ，這個答案就合法。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
ll l, r;
ll dp[22][222][222];
int dig[22], tot = 0, mod;
ll dfs (int now, int cnt, ll rem, int limit) {
//now：目前處理的數位。
//cnt：枚舉了的數位之和。
//rem：數字的總和模去mod後的得數。
//limit：标記是否到達邊界。
if (now > tot) {
if (cnt == 0) {//不符合題意。
return 0;
}
}
if (now > tot) {
if (rem == 0 && mod == cnt) {
//這是符合題意的情況。
return 1;
}
else {
return 0;
}
}
if (!limit && dp[now][cnt][rem] != -1) {
return dp[now][cnt][rem];
}
ll res = 0;
int up = limit ? dig[tot - now + 1] : 9;
for (int i = 0; i <= up; i ++) {
res += dfs (now + 1, cnt + i, (10 * rem + i) % mod, i == up && limit);
}
if (!limit) {
dp[now][cnt][rem] = res;
}
return res;
}
ll calc (ll x) {
tot = 0;
do {
dig[++tot] = x % 10;
x /= 10;
}while (x);
ll ans = 0;
for (mod = 1; mod <= 9 * tot; mod ++) {
//枚舉模數。
memset (dp, -1, sizeof (dp));
//每次都要初始化dp狀态。
ans += dfs (1, 0, 0, 1);
}
return ans;
}
int main() {
scanf ("%lld%lld", &l, &r);
printf ("%lld", calc (r) - calc (l - 1));
return 0;
}
![Apache 虛拟主機搭建過程[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)