HDU-3652 B-number

Posted on | In

题目链接

B-number
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 8748 Accepted Submission(s): 5196

Problem Description
A wqb-number, or B-number for short, is a non-negative integer whose decimal form
contains the sub- string “13” and can be divided by 13. For example, 130 and 2613
are wqb-numbers, but 143 and 2639 are not. Your task is to calculate how many
wqb-numbers from 1 to n for a given integer n.

Input
Process till EOF. In each line, there is one positive integer n(1 <= n <= 1000000000).

Output
Print each answer in a single line.

Sample Input

13
100
200
1000

Sample Output

1
1
2
2

题意： 求[1, n]中包含字段“13”且被13整除的数的个数

数位DP， 用pre代表前置状态， pre为0时表示前面没有“13”且前一数位不为1， pre为1时表示前面没有“13”且
前一位为1， pre为2时表示前面已有“13”。
若当前pre为2，则后续pre均为2。
若当前pre为1且当前数位为3， 则下一数位pre为2。
若当前pre为0或1且当前数位为1， 则下一数位pre为1
其余条件pre为0。

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
48
49
50
51
52
53
#include <bits/stdc++.h>
using namespace std;

int bit[20], tot;

long long dp[20][3][13];

long long dfs(int u, int pre, bool limits, int mod) {
    if (u == tot) {
        return (mod == 0) && (pre == 2);
    }
    if (!limits && dp[u][pre][mod] != -1) {
        return dp[u][pre][mod];
    }
    int top = limits ? bit[u] : 9;
    long long res = 0;
    for (int i = 0; i <= top; i++) {
        if (pre == 0) {
            res += dfs(u + 1, i == 1, limits && (i == top), (mod * 10 + i) % 13);
        }
        else if (pre == 1) {
            if (i == 3) {
                res += dfs(u + 1, 2, limits && (i == top), (mod * 10 + i) % 13);
            }
            else {
                res += dfs(u + 1, i == 1, limits && (i == top), (mod * 10 + i) % 13);
            }
        }
        else {
            res += dfs(u + 1, 2, limits && (i == top), (mod * 10 + i) % 13);
        }
    }
    if (!limits) dp[u][pre][mod] = res;
    return res;
}

long long solve(long long n) {
    tot = 0;
    while (n) {
        bit[tot++] = n % 10;
        n /= 10;
    }
    reverse(bit, bit + tot);
    memset(dp, -1, sizeof dp);
    return dfs(0, 0, 1, 0);
}

int main() {
    long long n;
    while (scanf("%lld", &n) == 1) {
        printf("%lld\n", solve(n));
    }
}