数位DP

Posted on Edited on In Word count in article: 514 Reading time ≈ 2 mins.
数位Dp

HDU3652 B-Number

这道题, 是非常典型的一个例子, 堪称数位\(Dp\)的模板

状态设计:

令\(Dp[Pos][Lst][Num]\)表示当前枚举的这个数是第\(Pos\)位, 前面数字的状态为\(Lst\), 前面的数的和对\(13\)取模的结果为\(Num\)

可以枚举第\(Pos\)为可能的值\(i\), 并有如下转移 \[ Ans=\sum\limits_{i=1}^{\min(limit,\;9)}Dp[pos-1][State][(Num*10+i)\%13] \] 解释一下\(State\): \[ \begin{align*} if (&State == 0)\\ &if (i == 1) return 1;\\ &else\;return 0;\\ else& if (State == 1)\\ &if (i == 1) return 1;\\ &else\;if (i == 3) return 2;\\ &else\;return 0;\\ retu&rn 2; \end{align*} \] 这应该算是比较明白的了

##Code

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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int M = 13;
int N, A[15], Dp[15][3][15];

inline int Get(int Lst, int Now)
{
    if (Lst == 0)
        if (Now == 1) return 1;
        else return 0;
    else if (Lst == 1)
        if (Now == 1) return 1;
        else if (Now == 3) return 2;
        else return 0;
    return 2;
}

int DFS(int Pos, int Lst, int Num, int Lim)
{
    if (Pos == 0) return Num == 0 && Lst == 2;
    if (!Lim && ~Dp[Pos][Lst][Num]) return Dp[Pos][Lst][Num];
    int Limit = Lim ? A[Pos] : 9, Ans(0);
    for (int i = 0; i <= Limit; ++i)
        Ans += DFS(Pos - 1, Get(Lst, i), (Num * 10 + i) % M, Lim && i == Limit);
    return Lim ? Ans : Dp[Pos][Lst][Num] = Ans;
}

inline int Work(int X)
{
    int Pos(0);
    while (X)
    {
        A[++Pos] = X % 10;
        X /= 10;
    }
    return DFS(Pos, 0, 0, 1);
}

int main()
{
    memset(Dp, -1, sizeof Dp);
    while (scanf ("%d", &N) != EOF) printf("%d\n", Work(N));
    system("pause");
}

#[ZJOI2010]数字计数

重复十次相同的操作……

因为考虑到有前导0, 会对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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
ll A, B;
ll Dp[20][20], Num[20];
ll DFS(int Pos, int Nmb, ll Sum, bool Lim, bool Led)
{
    if (Pos == 0) return Sum;
    if (!Lim && Led && ~Dp[Pos][Sum]) return Dp[Pos][Sum];
    int Up = Lim ? Num[Pos] : 9;
    ll Ans(0);
    for (int i = 0; i <= Up; ++i)
        Ans += DFS(Pos - 1, Nmb, Sum + ((i || Led) && (i == Nmb)), (i == Up) && Lim, Led || i);
    if (!Lim && Led) Dp[Pos][Sum] = Ans;
    return Ans;
}

inline ll Get(ll X, int N)
{
    memset (Dp, -1, sizeof Dp);
    int Len(0);
    while (X)
    {
        Num[++Len] = X % 10;
        X /= 10;
    }
    return DFS(Len, N, 0, 1, 0);
}

int main()
{
    scanf ("%lld %lld", &A, &B);
    for (int i = 0; i <= 9; ++i) printf ("%lld ", Get(B, i) - Get(A - 1, i));
    system ("pause");
}