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;
}
}