數(shù)位 DP 的技巧
本文意在探究對于數(shù)位 DP 題目的一些技巧。
首先我們應該清楚，數(shù)位 DP 一般而言處理答案大于大致 \(10^6\) 的題目。否則我們有技巧枚舉每個答案排序后查詢。
數(shù)位 DP 有兩種寫法，一種是迭代，一種是記憶化搜索。本文詳細介紹記憶化搜索，因為記憶化搜索好寫，好調(diào)，好想，這些都是在賽時的優(yōu)勢，而相比之下迭代不好寫，不好調(diào)，不好想，唯一的優(yōu)勢只有方便讀者理解數(shù)位 DP 的本質(zhì)。因為接下來的內(nèi)容做題有關，所以不討論迭代。
具體來說，我們記憶化搜索要記錄當前的位數(shù)和是否前面的數(shù)取到上界。除了這兩個狀態(tài)之外，我們還需要題目對數(shù)限制以及特殊答案貢獻的具體變量。
然后就是，因為取到上界的所有狀態(tài)都只會被計算一次，所以我們不記錄。
int f[pos][...];//不含 lim
...
int dfs(int pos,bool lim,...) {
}
首先我們從一道例題起手。
P1980 [NOIP 2013 普及組] 計數(shù)問題
考慮一下，如果 \(n\le 10^{10^3}\) 怎么做？
首先考慮限制，對于一個數(shù)，沒有限制。每個數(shù)都能夠?qū)Υ鸢肛暙I。
其次考慮一個數(shù)對答案的貢獻具體是多少，它對答案貢獻的值為各位上的數(shù)字等于 \(x\) 的個數(shù)，于是我們需要加入變量 \(sum\) 表示目前 \(1\) 到 \(pos\) 的位置上有多少個數(shù)等于 \(x\)，另外，對于 \(x=0\)，我們對答案的貢獻需要去除前導 \(0\)，所以記錄狀態(tài) \(zero\) 表示現(xiàn)在填 \(0\) 是否計入貢獻。
好的，現(xiàn)在所有狀態(tài)為 \(pos,lim,sum,zero\)。
\(zero,lim\) 兩個變量當然可以不計入記憶化狀態(tài)，但這題對空間的限制并不大，所以無所謂。
代碼：
// Problem: P1980 [NOIP 2013 普及組] 計數(shù)問題
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1980
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define int long long
#define upp(a, x, y) for (int a = x; a <= y; a++)
#define dww(a, x, y) for (int a = x; a >= y; a--)
#define pb(x) push_back(x)
#define endl '\n'
#define x first
#define y second
#define PII pair<int, int>
using namespace std;
const int N = 1e3 + 10;
int f[N][N][2];
int a[N];
int dfs(int pos, bool lim, bool zero, int sum, int p) {
if (!lim && f[pos][sum][zero] != -1) return f[pos][sum][zero];
if (!pos) return sum;
int res = 0;
int up = lim ? a[pos] : 9;
upp(i, 0, up) {
res = res + dfs(pos - 1, (lim && i == up), zero || (i),
sum + (zero && i == p), p);
}
if (lim == 0) f[pos][sum][zero] = res;
return res;
}
int solve(int x, int k) {
memset(f, -1, sizeof f);
int len = 0;
while (x) {
a[++len] = x % 10;
x /= 10;
}
return dfs(len, 1, (k != 0), 0, k);
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n, k;
cin >> n >> k;
cout << solve(n, k) << endl;
return 0;
}
再來一道。
-
所有數(shù)都能對答案貢獻。
-
每個數(shù)貢獻為所有數(shù)位之和，記錄狀態(tài) \(sum\) 表示當前數(shù)位之和。
-
整理狀態(tài) \(pos,lim,sum\)。
代碼：
// Problem: P4999 煩人的數(shù)學作業(yè)
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4999
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define int long long
#define upp(a, x, y) for (int a = x; a <= y; a++)
#define dww(a, x, y) for (int a = x; a >= y; a--)
#define pb(x) push_back(x)
#define endl '\n'
#define x first
#define y second
#define PII pair<int, int>
using namespace std;
const int N = 200, X = 1e9 + 7;
int f[N][N], a[N];
int dfs(int pos, int lim, int sum) {
if (f[pos][sum] != -1 && lim == 0) return f[pos][sum];
if (!pos) return sum;
int res = 0;
upp(i, 0, (lim ? a[pos] : 9)) {
(res += dfs(pos - 1, (lim && i == (lim ? a[pos] : 9)), sum + i) % X) %=
X;
}
if (lim == 0) f[pos][sum] = res;
return res;
}
int solve(int x) {
memset(f, -1, sizeof f);
int len = 0;
while (x) {
a[++len] = x % 10;
x /= 10;
}
return dfs(len, 1, 0);
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int qq;
cin >> qq;
while (qq--) {
int l, r;
cin >> l >> r;
cout << ((solve(r) - solve(l - 1)) % X + X) % X << endl;
}
return 0;
}
再來一道。
代碼源周賽 Round 11 E. [R11E]波浪數(shù)
-
一個數(shù)貢獻的條件是為波浪數(shù)，波浪數(shù)說白了就是一上一下，記錄這次應該是上還是下或者還未決定 \(go=1/0/2\)。如果還未決定，我們就可以填上繼續(xù) \(0\)，或者填上一個正數(shù)，然后決定上下是 \(0/1\) 各繼續(xù)計算，注意如果 \(pos=1\) 的時候，上和下都會只取到一個數(shù)，為了保證不重不漏，我們只再計算其中一種情況即可。對于之前就已經(jīng)決定是上還是下，我們直接枚舉數(shù)就行了，為了保證上下我們記錄狀態(tài) \(last\) 表示上一個填的數(shù)，沒什么好講的。
-
所有數(shù)的貢獻都為 \(1\)。
-
所有狀態(tài)為 \(pos,lim,go,last\)。
代碼：
#include <bits/stdc++.h>
#define int long long
#define upp(a, x, y) for (int a = x; a <= y; a++)
#define dww(a, x, y) for (int a = x; a >= y; a--)
#define pb(x) push_back(x)
#define endl '\n'
#define x first
#define y second
#define PII pair<int, int>
using namespace std;
const int N = 1e5 + 10, X = 998244353;
int f[N][3][10], a[N];
int dfs(int pos, bool lim, int go, int last) { // 0 代表降
if (f[pos][go][last] != -1 && lim == 0) return f[pos][go][last];
if (!pos) return 1;
int res = 0, up = (lim ? a[pos] : 9);
if (go == 2) {
upp(i, 0, up) {
if (i) {
if (pos > 1)
(res += dfs(pos - 1, (lim && i == a[pos]), 1, i)) %= X;
(res += dfs(pos - 1, (lim && i == a[pos]), 0, i)) %= X;
} else
(res += dfs(pos - 1, (lim && i == a[pos]), go, last)) %= X;
}
} else if (go == 1) {
upp(i, last + 1, up) {
(res += dfs(pos - 1, (lim && i == a[pos]), 0, i)) %= X;
}
} else {
upp(i, 0, min(last - 1, up)) {
(res += dfs(pos - 1, (lim && i == a[pos]), 1, i)) %= X;
}
}
if (!lim) f[pos][go][last] = res;
return res;
}
int solve(string x) {
int len = 0;
dww(i, x.size() - 1, 0) { a[++len] = x[i] - '0'; }
return dfs(len, 1, 2, 0);
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
memset(f, -1, sizeof f);
int qq;
cin >> qq;
while (qq--) {
string l, r;
cin >> l >> r;
int ans = ((solve(r) - solve(l)) % X + X) % X;
int now = 2, flag = 1;
upp(i, 1, (int)l.size() - 1) {
if (l[i] == l[i - 1]) {
flag = 0;
break;
}
if (now == 2) {
if (l[i] > l[i - 1])
now = 0;
else
now = 1;
} else {
if (now && l[i] < l[i - 1]) {
flag = 0;
break;
}
if (!now && l[i] > l[i - 1]) {
flag = 0;
break;
}
now ^= 1;
}
}
if (flag || l.size() == 1) ans++;
cout << ans % X << endl;
}
return 0;
}
浙公網(wǎng)安備 33010602011771號