mydcwfy's Blog

数位 DP

Posted on
Symbols count in article: 6.9k Reading time ≈ 15 mins.

比较套路的一种 DP。

数位 DP

1. 通用思路

1）通用问法

  1. 首先，题目会让你求一个区间中满足一个条件的数。
  2. 该条件可以被拆分为逐数位考虑的方法。

2）通用解法

  1. $[L,R]\Rightarrow[1,R]-[1,L-1]$
  2. 考虑填入第 $i$ 位时，可以分为 $[0,a_{i}-1]$ 和 $a_i$ 两种情况，其中 $a_i$ 表示限制数目第 $i$ 位的数字。

2. 例题

T1：度的数量

题目传送门 AcWing

按上面的做法来分析，如果选 $0$，那么答案为 $\binom{n-1}k$，如果选 $1$ 且 $a_i\not=1$，那么答案为 $\binom{n-1}{k-1}$。

如果 $a_i=1$，那么就填上 1，递归即可。

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 35;
int f[N][N];
int K, B, l, r;

void init()
{
    for (int i = 0; i < N; ++ i )
        for (int j = 0; j <= i; ++ j )
            if (!j) f[i][j] = 1;
            else f[i][j] = f[i - 1][j] + f[i - 1][j - 1];
}

int dp(int maxn)
{
    if (!maxn) return !K;

    vector <int> nums;
    int tmp = maxn;
    while (tmp) nums.push_back(tmp % B), tmp /= B;

    int res = 0, last = 0;
    for (int i = nums.size() - 1; i >= 0; -- i )
    {
        int &x = nums[i];
        if (x)
        {
            res += f[i][K - last];
            if (x > 1)
            {
                if (K >= last + 1) res += f[i][K - last - 1];
                break;
            }
            else{
                last ++ ;
                if (last > K) break;
            }
        }

        if (!i && last == K) res ++ ; 
    }

    return res;
}

int main()
{
    init();

    cin >> l >> r >> K >> B;

    cout << dp(r) - dp(l - 1) << endl;

    return 0;
}

T2：[SCOI2009] Windy 数

题目传送门 Luogu

题目传送门 AcWing

题目传送门 LOJ

本题同样是数位 DP 的经典题目。

仍然从高到低枚举每一位，分为 $[0,a_i-1]$ 和 $a_i$ 两种情况。

首先，我们发现，当前的位既不能超过 $a_i$，又必须与 $a_{i+1}$ 差值至少为 2。

枚举当前位即可，后面的位就与当前数无关，就可以预处理了。

具体来说，我们预处理 $f[i,j]$ 为位数为 $i$，且最高位为 $j$ 的总数。

这个显然不难，一个简单的递推即可。

但是，本题还有一个问题：不含前导零怎么处理？

首先，我们将和当前限制的数的相同位数的算出来（即第一位至少为 1，后面可以为 0），然后再将低于当前限制位数算出来，很明显我们已经预处理了。

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 12;
int f[N][N];

void init()
{
    for (int j = 0; j <= 9; ++ j ) f[1][j] = 1;
    for (int i = 2; i < N; ++ i )
        for (int j = 0; j <= 9; ++ j )
            for (int k = 0; k <= 9; ++ k )
                if (abs(k - j) >= 2) f[i][j] += f[i - 1][k];
}

int dp(int n)
{
    if (!n) return 0;

    vector <int> nums;
    nums.clear();
    while (n) nums.push_back(n % 10), n /= 10;

    int res = 0, last = -2;

    for (int i = nums.size() - 1; i >= 0; -- i )
    {
        int &x = nums[i];
        for (int j = i == nums.size() - 1; j < x; ++ j )
            if (abs(j - last) >= 2) res += f[i + 1][j];
        if (abs(x - last) >= 2) last = x;
        else break;
        if (!i) res ++;
    }
    // printf("%d\n", res);
    for (int i = nums.size() - 2; i >= 0; -- i )
        for (int j = 1; j <= 9; ++ j ) res += f[i + 1][j];
    return res;
}

int main()
{
    init();
    int l, r;
    cin >> l >> r;
    cout << dp(r) - dp(l - 1) << endl;
    return 0;
}

T3：数字游戏

题目传送门 LOJ

可以发现，所有数位 DP 的题目其实差不多。

直接预处理 $i$ 位数，最高位是 $j$，且模 $n$ 是 $k$ 的总个数。

然后和上题差不多。

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

typedef long long ll;
const int N = 105;

ll f[12][10][N];
int n;

inline int Mod(int s)
{
    return (s % n + n) % n;
}

void init()
{
    memset(f, 0, sizeof f);
    for (int i = 0; i <= 9; ++ i) f[1][i][i % n] = 1;

    for (int i = 2; i < 12; ++ i)
        for (int j = 0; j <= 9; ++ j)
            for (int k = 0; k < n; ++ k)
                for (int l = 0; l <= 9; ++l)
                    f[i][j][k] += f[i - 1][l][Mod(k - j)];
}

ll dp(int x)
{
    if (!x) return 1;

    vector <int> nums;
    while (x) nums.push_back(x % 10), x /= 10;

    ll res = 0;
    int last = 0;
    for (int i = nums.size() - 1; i >= 0; -- i)
    {
        int &x = nums[i];
        for (int j = 0; j < x; ++ j)
            res += f[i + 1][j][Mod(-last)];
        last = Mod(last + x);
        
        if (!i && !last) res ++;
    }
    return res;
}

int main()
{
    int a, b;
    while (cin >> a >> b >> n) init(), printf("%lld\n", dp(b) - dp(a - 1));

    return 0;
}

剩下几个题作为练习的题目，不再做讲解，有疑问的同学可以看代码。

T4：不要 62

题目传送门 LOJ

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
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 12;
int f[N][10];

void init()
{
    for (int i = 0; i <= 9; ++ i) f[1][i] = i != 4;

    for (int i = 2; i < N; ++ i)
        for (int j = 0; j <= 9; ++ j)
            for (int k = 0; k <= 9; ++ k)
            {
                if (j == 4 || k == 4 || (j == 6 && k == 2)) continue;
                f[i][j] += f[i - 1][k];
            }
}

int dp(int n)
{
    if (!n) return 1;

    vector <int> nums;
    while (n) nums.push_back(n % 10), n /= 10;

    int res = 0, last = 0;
    for (int i = nums.size() - 1; i >= 0; -- i)
    {
        int &x = nums[i];
        for (int j = 0; j < x; ++ j)
            if ((j != 2 || last != 6) && (j != 4))
                res += f[i + 1][j];
        if ((last == 6 && x == 2) || (x == 4)) break;
        last = x;
        if (!i) res ++;
    }
    return res;
}

int main()
{
    init();
    int a, b;
    
    while (cin >> a >> b, a || b) printf("%d\n", dp(b) - dp(a - 1));

    return 0;
}

T5：恨 7 不成妻

题目传送门 LOJ

维护 $s0,s1,s2$ 分别表示所有的 0 次方（及个数），1 次方（和），2 次方。

比较难写，特别注意是模什么。

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define mod(x, y) ((x) % (y) + (y)) % (y)
using namespace std;

typedef long long ll;
const int N = 25;
const ll Mod = 1e9 + 7;
struct Node
{
    ll s0, s1, s2;
    inline void adjust()
    {
        s0 = mod(s0, Mod);
        s1 = mod(s1, Mod);
        s2 = mod(s2, Mod);
    }
};

Node f[N][10][8][8];
ll p7[N], pm[N];

void merge(Node &v1, const Node &v2, int j, ll p)
{
    v1.s0 = (v1.s0 + v2.s0) % Mod;
    v1.s1 = ((v1.s1 + v2.s1) % Mod + v2.s0 * p % Mod * (ll)j % Mod) % Mod;
    v1.s2 = (v1.s2 + v2.s2
            +2ll * p % Mod * v2.s1 % Mod * (ll)j % Mod
            +((ll)j * p % Mod) * ((ll)j * p % Mod) % Mod * v2.s0 % Mod) % Mod;
}

void init()
{
    memset(f, 0, sizeof(f));
    p7[0] = pm[0] = 1;
    for (int i = 1; i < N; ++ i) p7[i] = (p7[i - 1] * 10ll) % 7ll;
    for (int i = 1; i < N; ++ i) pm[i] = (pm[i - 1] * 10ll) % Mod;
    for (int i = 0; i <= 9; ++ i)
    {
        Node &v1 = f[1][i][i % 7][i % 7];
        if (i == 7) continue;
        v1.s0 ++, v1.s1 += i, v1.s2 += i * i;
    }
    ll p = 10ll;
    for (int i = 2; i < N; ++ i, p *= 10ll, p %= Mod)
        for (int j = 0; j <= 9; ++ j)
        {
            if (j == 7) continue;
            for (int k = 0; k <= 9; ++ k)
                for (int x = 0; x < 7; ++ x)
                    for (int y = 0; y < 7; ++ y)
                    if (k != 7) merge(f[i][j][x][y],
                     f[i - 1][k][mod(x - j, 7ll)][mod(y - p7[i - 1] * j, 7ll)], j, p);
        }
}

Node calc(int i, int j, int x, int y)
{
    ll s0 = 0, s1 = 0, s2 = 0;
    for (int k = 0; k < 7; ++ k)
        for (int l = 0; l < 7; ++ l)
            if (k != x && l != y)
            {
                Node &v = f[i][j][k][l];
                s0 = (s0 + v.s0) % Mod;
                s1 = (s1 + v.s1) % Mod;
                s2 = (s2 + v.s2) % Mod;
            }
    return (Node){s0, s1, s2};
}

ll dp(ll n)
{
    if (!n) return 0;

    ll tmp = n;n %= Mod;
    vector <int> nums;
    while (tmp) nums.push_back(tmp % 10), tmp /= 10;

    ll last0 = 0, last1 = 0, res = 0;
    for (int i = nums.size() - 1; i >= 0; -- i)
    {
        int &x = nums[i];
        for (int j = 0; j < x; ++ j)
        {
            if (j == 7) continue;
            int a = mod(-last0, 7), b = mod(-(last1 % 7) * p7[i + 1], 7);
            Node v = calc(i + 1, j, a, b);
            res = (res + (last1 % Mod) * (last1 % Mod) % Mod * pm[i + 1] % Mod * pm[i + 1] % Mod * v.s0 % Mod
            + 2 * (last1 % Mod) % Mod * pm[i + 1] % Mod * v.s1 % Mod + v.s2) % Mod;
            // cout << res << endl;
        }

        if (x == 7) break;

        last1 = last1 * 10 + x;last0 += x;
        if (!i && last1 % 7 && last0 % 7) res = (res + n * n % Mod) % Mod;
        
    }
    return res;
}

signed main()
{
#ifndef ONLINE_JUDGE
    freopen("L10168.in", "r", stdin);
    freopen("myans.out", "w", stdout);
#endif
    init();

    ll t, l, r;cin >> t;
    while (t --)
    {
        cin >> l >> r;
        cout << mod(dp(r) - dp(l - 1), Mod) << endl;
    }

    return 0;
}