DDOSvoid's Blog

浅谈数位DP

发表于 更新于 分类于
本文字数： 5.7k 阅读时长 ≈ 5 分钟

简介

虽说题目是浅谈，但其实主要是讲我在写数位dp时遇到的问题

数位DP记忆化搜索写法中不用种类变量的总结

我平时在写数位dp的时候都是使用记搜，然而我一直没有搞懂这东西的复杂度

所以来这里稍微总结一下

首先根据数据的组数我们将题目分成两类：单组数据和多组数据

然后根据组数的不同我们将记搜中的变量分成两类（忽略pos和lead

根据每组数据的输入变化的变量，数据相关变量

与每组数据无关的变量，数据无关变量

以Luogu P2657 [SCOI2009] windy 数为例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring> 
#define maxn 11 
#define ll long long 
using namespace std;

int a, b;

int f[maxn][maxn], d[maxn], len; 
int dfs(int pos, bool limit, bool lead, int pre) {
    if (!pos) return 1;
    if (!limit && !lead && ~f[pos][pre]) return f[pos][pre];
    int up = limit ? d[pos] : 9; ll sum = 0; 
    for (int i = 0; i <= up; ++i) {
        if (abs(i - pre) < 2 && !lead) continue;
        sum += dfs(pos - 1, limit && i == d[pos], lead && !i, i);
    }
    if (!limit && !lead) f[pos][pre] = sum;
    return sum;
}

int solve(int x) { len = 0; 
    while (x) {
        d[++len] = x % 10; 
        x /= 10;
    } 
    return dfs(len, 1, 1, 0); 
} 

int main() {
    cin >> a >> b; memset(f, -1, sizeof f); 
    cout << solve(b) - solve(a - 1) << endl; 
    return 0;
}

能够发现limit是数据相关变量，pre是数据无关变量

进一步观察两个变量的特性，能够发现，我们并没有将limit记录在数组中，而是将pre记录在数组中

由此可以总结出一般情况下不需要将数据相关变量记录在数组中，而需要将数据无关变量记录在数组中

但是将数据相关变量放进数组里，在多组数据时可能会降低复杂度，不过对于limit来说需要改成当前位的上界来进行记录

所以我们在此再次将数据相关变量分类，简化数据相关变量和复杂数据相关变量

简化数据变量一般直接扔到dfs的参数列表里，而复杂数据变量则被扔到数组中

以hdu 4252 XHXJ’s LIS为例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 20
#define maxm 11
#define ll long long
using namespace std;

int n; ll a, b; 

int L[1 << maxm];
void init() {
    int M = (1 << maxm) - 1, m = 10; 
    for (int S = 1; S <= M; ++S) 
        for (int i = 1; i <= m; ++i) L[S] += S >> i - 1 & 1;
}
 
int calc(int S, int k) {
    for (int i = k; i < 10; ++i) 
        if (S >> i & 1) { S ^= 1 << i; break; } 
    S |= 1 << k; return S; 
} 
    

ll f[maxn][1 << maxm][maxm]; int K, d[maxn], len; 
ll dfs(int pos, int lead, int limit, int S, int k) {
    if (!pos) return L[S] == k; 
    if (!lead && !limit && ~f[pos][S][k]) return f[pos][S][k];
    int up = limit ? d[pos] : 9; ll ans = 0;
    for (int i = 0; i <= up; ++i) {
        if (lead && !i) { ans += dfs(pos - 1, 1, 0, 0, k); continue; }
        ans += dfs(pos - 1, 0, limit && i == d[pos], calc(S, i), k);
    }
    if (!lead && !limit) f[pos][S][k] = ans;
    return ans;
}

ll solve(ll x) { len = 0;
    while (x) { 
        d[++len] = x % 10;
        x /= 10;
    }
    return dfs(len, 1, 1, 0, n);
}

int icase; 
void work() { 
    cin >> a >> b >> n;
    printf("Case #%d: %lld\n", ++icase, solve(b) - solve(a - 1)); 
}

int main() {
    int T; cin >> T; init(); memset(f, -1, sizeof f); 
    while (T--) work(); 
    return 0;
}

为了不在每组数据时都进行初始化，我们将k变成复杂数据相关变量并放入数组中，这样才能起到降低复杂度的作用

那么在单组数据的情况下，简化数据相关变量是否能对dp的复杂度或者常数进行优化，我认为这取决于不同的题目（实际上是我不知道还要如何对简化数据相关变量分类了

对于数据相关变量对时间复杂度的

以[SDOI2016]储能表 为例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 70 
#define ll long long
using namespace std;

ll n, m, k; int p;

struct node {
    int s, v; 

    node() {}
    node(int _v, int _s) { v = _v; s = _s; } 
} f[maxn][2][2][2];

int d1[maxn], d2[maxn], d3[maxn]; 
node dfs(int pos, bool lim1, bool lim2, bool lim3) {
    if (!pos) return node(0, 1);
    if (~f[pos][lim1][lim2][lim3].v || ~f[pos][lim1][lim2][lim3].s) return f[pos][lim1][lim2][lim3];
    int up1 = lim1 ? d1[pos] : 1, up2 = lim2 ? d2[pos] : 1; node ans = node(0, 0);
    for (int i = 0; i <= up1; ++i)
        for (int j = 0; j <= up2; ++j) {
            if (lim3 && (i ^ j) < d3[pos]) continue;
            node t = dfs(pos - 1, lim1 && i == d1[pos], lim2 && j == d2[pos], lim3 && (i ^ j) == d3[pos]);
            ans.s = (ans.s + t.s) % p;
            ans.v = (ans.v + t.v + (i ^ j) * (1ll << pos - 1) % p * t.s) % p;
        }
    return f[pos][lim1][lim2][lim3] = ans; 
}

node solve(ll x1, ll x2, ll x3) { 
    int l1 = 0, l2 = 0, l3 = 0;
    memset(d1, 0, sizeof d1); memset(d2, 0, sizeof d2); memset(d3, 0, sizeof d3); 
    while (x1) {
        d1[++l1] = x1 % 2;
        x1 /= 2;
    }
    while (x2) {
        d2[++l2] = x2 % 2;
        x2 /= 2;
    }
    while (x3) {
        d3[++l3] = x3 % 2;
        x3 /= 2;
    }
    int l = max(l1, max(l2, l3)); 
    return dfs(l, 1, 1, 1);
}

void mem() {
    for (int i = 0; i < maxn; ++i)
        for (int j = 0; j < 2; ++j)
            for (int k = 0; k < 2; ++k)
                for (int l = 0; l < 2; ++l) f[i][j][k][l] = node(-1, -1); 
}

void work() {
    cin >> n >> m >> k >> p; --n; --m; 
    mem(); node t = solve(n, m, k); 
    cout << (t.v - t.s * (k % p) % p + p) % p << endl;
}

int main() {
    int T; cin >> T;
    while (T--) work();
    return 0;
}

注意到我们在这道题里记录了三个limit变量，按照我们之前的题目，似乎limit已经默认不会减小算法复杂度了

但在此题中，limit变量不仅是作为简化数据相关变量出现，且使得复杂度变正常了

即是不记录这些变量也可以，但是时间复杂度会爆炸，约等于爆搜了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
node dfs(int pos, bool lim1, bool lim2, bool lim3) {
    if (!pos) return node(0, 1);
    if (!lim1 && !lim2 && !lim3 && (~f[pos].v || ~f[pos].s)) return f[pos];
    int up1 = lim1 ? d1[pos] : 1, up2 = lim2 ? d2[pos] : 1; node ans = node(0, 0);
    for (int i = 0; i <= up1; ++i)
        for (int j = 0; j <= up2; ++j) {
            if (lim3 && (i ^ j) < d3[pos]) continue;
            node t = dfs(pos - 1, lim1 && i == d1[pos], lim2 && j == d2[pos], lim3 && (i ^ j) == d3[pos]);
            ans.s = (ans.s + t.s) % p;
            ans.v = (ans.v + t.v + (i ^ j) * (1ll << pos - 1) % p * t.s) % p;
        }
    if (!lim1 && !lim2 && !lim3) f[pos] = ans;
    return ans; 
}

我们来算一下复杂度在哪里出了问题，假设只扔掉了lim1

那么我们考虑在lim1为真的时候且i==d1[pos]时，对于第二层循环到下一层dfs的任何都无法保存，且当下一层也出现i==d1[pos]时，此时计算复杂度应为 $O(2^{70})$

换句话说扔掉lim2和lim3都不行，因为他们都影响到了i和j的循环

那么我们在最后再次总结一下这三种变量

首先是数据无关变量和数据相关变量

字面意思上的区分就是看跟当前组输入的关系

简化数据相关变量和复杂数据相关变量

复杂数据相关变量是指将只能在单组使用的简化相关变量复杂化以适配所有数据

简化相关变量和复杂相关变量都可以用来降低时间复杂度

数位DP复杂度的计算

以下说法可能存在大量错误

比较一般的计算方法是状态的数量乘上一个状态转移到另一个状态的时间

但这是在不考虑简化数据相关变量的情况下

存在这种变量的情况要特殊分析

例题

  1. 简要题意：给定 $n,l,r,z$，求有多少个长度为 $n$ 的序列 $a_i$，满足 $l\le\sum_{i=1}^na_i\le r$ 且 $\bigoplus_{i=1}^na_i=z$，其中 $\oplus$ 为异或

    $n\le 1000,1\le l,r \le 10^{18},z\le 10^{18}$

    简要题解：考虑数位 $dp$，我们令 $f[o][i]$ 表示填到了第 $o$ 位，第 $o$ 位最多能选 $i$ 个 $1$，注意到 $f[o][i]$ 向 $f[o-1][k]$ 转移时，能选的 $1$ 的个数为 $i\times 2$ 加上第 $o-1$ 位是否为 $1$，注意到我们一次最多只能选 $n$ 个 $1$，所以我们第二维对 $n$ 取 $min$ 即可

    时间复杂度 $O(64n^2)$，注意并不需要使用记忆化搜索

    CF 1670F Jee, You See?