B-number
time limit per test 3.5 second memory limit per test 256 megabytes
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.

传送门：HDU3652

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

1
2
3
4
13
100
200
1000

Sample Output

1
2
3
4
1
1
2
2

题解

数位dp 记忆化搜索板子
## AC 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
import java.io.*;  
import java.util.*;  
public class Main {  
static long[][][]dp=new long[15][13][3];  
static int[]dig=new int[15];  
    public static void main(String[] args) {  
        FastScanner sc=new FastScanner();  
        PrintWriter pw=new PrintWriter(System.out);  
        while(sc.hasNext()){  
            for(int i=0;i<12;i++)  
                for(int j=0;j<13;j++)  
                Arrays.fill(dp[i][j],-1);  
            int l=sc.nextInt();  
            pw.println(solve(l));  
            pw.flush();  
        }  
    }  
    static long solve(int x){  
        int cnt = 0;  
        while(x>0){  
            dig[cnt ++] = x % 10;  
            x = x / 10;  
        }  
        return dfs(cnt - 1, 0 ,0, true);  
    }  
    static long dfs(int len,int mod,int have,boolean flag){//长度，前面传递的信息，是否受到目标的限制  
        if(len < 0){  
            if(mod==0&&have==2)  
                return 1;  
            else  
                return 0;  
        }  
        if(!flag&& dp[len][mod][have] != - 1){//记忆话搜索  
            return dp[len][mod][have];  
        }  
        int end = flag ? dig[len] : 9;//判断是否受到限制  
        long ans = 0;  
        for(int i = 0 ; i <= end ; ++ i){//在遇到非法情况的时候直接斩掉。。当然也可以保存所有的非法情况再用合法的减去。因为这题数据范围小，随意    
            int modi=(mod*10+i)%13;  
            int havex=have;  
            if(have==0&&i==1)havex=1;  
            if(have==1&&i!=1)havex=0;  
            if(have==1&&i==3)havex=2;  
            ans += dfs(len - 1 ,modi,havex, flag && i == end);//结尾的标记  
        }  
        if(!flag){  
            dp[len][mod][have] = ans;  
        }  
        return ans;  
    }  
}