B-number

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7415 Accepted Submission(s): 4346

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

Author

wqb0039

Source

2010 Asia Regional Chengdu Site —— Online Contest

题解：

求一段区间内既含有“13”也能被13整除的数的个数，数位DP。

1.dp[pos][status][num]：第pos位，状态为status（2为含有“13”， 1为不含有“13”但末尾为“1”， 0为什么都不满足），num为当前的数除以13的余数。

2.题目的其中一个要求是：该数能够被13整除，那么为什么在dp的数组中，只用记录：到当前位所形成的数除以13的余数呢？答：

比如 “14XXX” ：

即当前位为4，上一位为1，后面位的数待定。所以到当前位为止，数字为14，那么14%13 = 1 。

由于当前位为第四位，即最小单元为1000，所以上面的 14%13 = 1 实际是： 14000 % 13000 = 1000。由于13000是13的倍数，故14000 除以 13，至少能减少13000，剩下1000，这个1000只能到下一位才能继续处理了。也就是说： “14XXX” 和 “01XXX” 对于模13来说是等价的，因为“14XXX”可以减掉13000得到“01XXX”。

故：对于位置相同，且到当前位所形成的数字%13相等的状态，实际上可以归为一类。

代码如下：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <vector>
 6 #include <cmath>
 7 #include <queue>
 8 #include <stack>
 9 #include <map>
10 #include <string>
11 #include <set>
12 using namespace std;
13 typedef long long LL;
14 const int INF = 2e9;
15 const LL LNF = 9e18;
16 const int mod = 1e9+7;
17 const int maxn = 20+10;
18 
19 int a[maxn], dp[maxn][3][15];
20 
21 int dfs(int pos, int status, int num,  bool lim)
22 {
23     if(!pos) return (status==2)&&(num==0);  //含有“13”，且能够被“13”整除
24     if(!lim && dp[pos][status][num]!=-1) return dp[pos][status][num];
25 
26     int ret = 0;
27     int m = lim?a[pos]:9;
28     for(int i = 0; i<=m; i++)
29     {
30         int tmp_status;
31         if(status==2 || status==1 && i==3)  //含有“13”
32             tmp_status = 2;
33         else if(i==1)               //前面的位不含有“13”， 但当前位（末尾）为“1"。（满足了一部分）
34             tmp_status = 1;
35         else                        //前面的位不含有“13”，且当前位不是“1”。
36             tmp_status = 0;
37 
38         // (num*10+i)%13：只需记录%13的余数，而不用记录完整的数
39         ret += dfs(pos-1, tmp_status, (num*10+i)%13, lim&&(i==m));
40     }
41 
42     if(!lim) dp[pos][status][num] = ret;
43     return ret;
44 }
45 
46 int main()
47 {
48     int n;
49     memset(dp,-1, sizeof(dp));
50     while(scanf("%d",&n)!=EOF)
51     {
52         int p = 0;
53         while(n)
54         {
55             a[++p] = n%10;
56             n /= 10;
57         }
58         LL ans = dfs(p, 0, 0, 1);
59         printf("%d
",ans);
60     }
61 }

View Code