数位dp

//hdu 2089

不要62

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 60338 Accepted Submission(s): 23843

Problem Description

杭州人称那些傻乎乎粘嗒嗒的人为62（音：laoer）。
杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。
不吉利的数字为所有含有4或62的号码。例如：
62315 73418 88914
都属于不吉利号码。但是，61152虽然含有6和2，但不是62连号，所以不属于不吉利数字之列。
你的任务是，对于每次给出的一个牌照区间号，推断出交管局今次又要实际上给多少辆新的士车上牌照了。

Input

输入的都是整数对n、m（0<n≤m<1000000），如果遇到都是0的整数对，则输入结束。

Output

对于每个整数对，输出一个不含有不吉利数字的统计个数，该数值占一行位置。

Sample Input

1 100 0 0

Sample Output

Author

qianneng

Source

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <vector>
 6 #include <queue>
 7 #include <set>
 8 #include <map>
 9 #include <string>
10 #include <cmath>
11 #include <cstdlib>
12 #include <ctime>
13 using namespace std;
14 typedef long long ll;
15 const ll mod = 1e9+7;
16 int  n,m,d[20],dp[20][2];
17 //dp[pos][state]:state 前一位是6吗
18 int dfs(int pos,bool  state,bool limit)
19 {
20     if(pos==0) return 1;
21     //如果有limit 肯定是不行的
22     if(!limit&&dp[pos][state]!=-1) return dp[pos][state];//避免重复
23      //为什么要返回呢？可以画图理解当我们搜到3XXX时，程序运行到
24      //1XXX时就已经把3XXX之后的搜索完了，记忆化也是这个用意.
25     int sum=0,up=limit?d[pos]:9;//up ：上限
26     for(int  i=0;i<=up;i++){
27         if(i==4||(state&&i==2)) continue;//state:i==6
28         else{
29             sum+=dfs(pos-1,i==6,limit&&i==d[pos]);//只有之前有限制现在又达到了上限
30         }
31     }
32     if(!limit) dp[pos][state] = sum;
33     return  sum;
34 }
35 int  solve(int  x){
36     int pos=0;
37     while(x){
38         d[++pos]=x%10;
39         x/=10;
40     }
41     return dfs(pos,false,true);//最高位：state一定false(!=6) limit 一定有
42 }
43 int  main()
44 {
45     while(~scanf("%d%d",&n,&m)){
46         if(n==0&&m==0) break;
47         memset(dp,-1,sizeof(dp));//易忘
48         printf("%d
",solve(m)-solve(n-1));
49     }
50     return 0;
51 }

华东交通大学2018年ACM“双基”程序设计竞赛

7的意志

定义一个序列a:7,77,777......,7777777(数字全为7的正整数，且长度可以无限大）
clearlove7需要从含有7的意志的数里获得力量，如果一个整数能被序列a中的任意一个数字整除，并且其数位之和为序列a中任意一个数字的倍数，那么这个数字就含有7的意志，现在给你一个范围[n,m]，问这个范围里有多少个数字含有7的意志。

输入描述:

多组输入，每行两个个整数n，m（1<=n<=m<=1e18)，如果输入为"0 0"，停止程序。

输出描述:

每一行输出含有7的意志的数的个数。

示例1

输入

复制

输出

复制

1
3
21

说明

1到100中符合条件的数字为7，70，77

 1 j//就是%7 
 2 #include <cstdio>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <cmath>
 6 #include <cstring>
 7 using namespace std;
 8 #define ll long long
 9 const int mod=1e9+7;
10 //ll dp[21][9][9]:20+1，8+1 不然会数组越界
11 ll dp[21][9][9];//dp[pos][sum1][sum2]:pos：第几位，
12 //  sum1 :从第一位到第pos位的数%7的值
13 // sum2 :从第一位到第pos位的数的和%7的值
14 // 123 sum1 : 1 (1*10+2)%7==5 (5*10+3)%7==4
15 //123 sum2 : 1 3 6 
16 ll  d[20];
17 void  init()
18 {
19     for(int  i=0;i<=20;i++){
20         for(int j=0;j<=8;j++){
21             for(int k=0;k<=8;k++){
22                 dp[i][j][k]  = -1;
23             }
24         }
25     }
26 }
27 ll dfs(int pos,int  sum1,int  sum2,bool limit){
28     if(pos==0) return (sum1%7==0&&sum2%7==0);
29     if(!limit&&dp[pos][sum1][sum2]!=-1) return  dp[pos][sum1][sum2];
30     int up=limit?d[pos]:9;
31     ll ret = 0;
32     for(int i=0;i<=up;i++){
33         ret+=dfs(pos-1,(sum1*10+i)%7,(sum2+i)%7,limit&&i==d[pos]);
34     }
35     if(!limit) {
36         dp[pos][sum1][sum2] = ret;
37     }
38     return  ret;
39 }
40 ll solve(ll x){    
41     int pos= 0;
42     while(x)
43     {
44         d[++pos] =x%10;
45         x/=10;        
46     }    
47     return dfs(pos,0,0,true);//pos==0才算一个，因此pos时sum1,sum2都为0
48 }
49 ll n,m;
50 int  main()
51 {
52     init();//类似于预处理
53     while(~scanf("%lld%lld",&n,&m)){
54         if(n==0&&m==0) break;
55         solve(m);
56         printf("%lld
",solve(m)-solve(n-1));
57     }
58     return  0;
59 }