HDU3652(数位dp)

A - B-number

Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u

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

Sample Output

1
1
2
2

数位dp

 1 //2016.8.7
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<string>
 6 
 7 using namespace std;
 8 
 9 int dp[12][13][2][3];
10 //dp[i][j][k][p]表示方法数,i表示已处理的长度，j表示mod13的余数，k表示前缀是否相同(0为相同，1为不同),p为1表示前一个数为1,为2表示已出现13，否则为0
11 int mi[12];
12 
13 int cal(int x, int n, int p)
14 {
15     return x*mi[n]%p;
16 }
17 
18 int judge(int x)//三态函数
19 {
20     if(x==1)return 1;
21     else if(x==3)return 2;
22     else return 0;
23 }
24 
25 int solve(string s)
26 {
27     memset(dp, 0, sizeof(dp));
28     dp[0][0][1][0] = 1;
29     int len = s.size();
30     for(int i = 0; i < len; i++)
31       for(int j = 0; j < 13; j++)
32         for(int k = 0; k < 2; k++)
33           for(int p = 0; p < 3; p++)
34           {
35               if(dp[i][j][k][p]!=0)
36               {
37                   int l, r;
38                   l = 0; r = (k==1?s[i]-'0':9);
39                   for(int x = l; x <= r; x++)
40                   {
41                       if(p==0)
42                       dp[i+1][(j+cal(x, len-i-1, 13))%13][(k==1&&x==r)?1:0][x==1?1:0]+=dp[i][j][k][p];
43                       else if(p==1)
44                       dp[i+1][(j+cal(x, len-i-1, 13))%13][(k==1&&x==r)?1:0][judge(x)]+=dp[i][j][k][p];
45                       else if(p==2)
46                       dp[i+1][(j+cal(x, len-i-1, 13))%13][(k==1&&x==r)?1:0][2]+=dp[i][j][k][p];
47                   }
48               }
49           }
50     return dp[len][0][0][2] + dp[len][0][1][2];
51 }
52 
53 int main()
54 {
55     string n; 
56     while(cin>>n)
57     {
58         mi[0] = 1;
59         for(int i = 1; i < 12; i++)
60           mi[i] = mi[i-1]*10%13;
61         int ans;
62         ans = solve(n);
63         cout<<ans<<endl;
64     }
65 
66     return 0;
67 }