数字游戏

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=1e5+5;
 4 int tot,e[20];
 5 long long c[20][20];
 6 int a,b;
 7 template<class t>void red(t &x)
 8 {
 9     int w=1;
10     x=0;
11     char ch=getchar();
12     while(ch>'9'||ch<'0')
13     {
14         if(ch=='-')
15             w=-1;
16         ch=getchar(); 
17     }
18     while(ch>='0'&&ch<='9')
19     {
20         x=(x<<3)+(x<<1)+ch-'0';
21         ch=getchar();
22     } 
23     x*=w;
24 } 
25 void input()
26 {
27     freopen("input.txt","r",stdin);
28 }
29 void dv(int x)
30 {
31     tot=0;
32     while(x)
33     {
34         e[++tot]=x%10;
35         x/=10;
36     }
37     e[tot+1]=0;
38 }
39 long long dfs(int pos,bool limit,bool zero,int pre)
40 {
41     if(pos==0)
42         return 1;
43     if(!limit&&zero&&~c[pos][pre])
44         return c[pos][pre];
45     int up=limit?e[pos]:9;
46     int ans=0;
47     for(int i=pre;i<=up;++i)
48         ans+=dfs(pos-1,limit&&(i==up),zero||i,i);
49     if(!limit&&zero)
50         c[pos][pre]=ans;
51     return ans;
52 }
53 long long solve(int x)
54 {
55     dv(x);
56     memset(c,-1,sizeof(c));
57     return dfs(tot,1,0,0);
58 }
59 int main()
60 {
61     input();
62     while(scanf("%d%d",&a,&b)==2)
63         printf("%lld
",solve(b)-solve(a-1));
64     return 0;
65 }

1 不降数

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=1e5+5;
 4 int tot,e[20];
 5 int a,b,mod;
 6 long long c[20][105];
 7 template<class t>void red(t &x)
 8 {
 9     int w=1;
10     x=0;
11     char ch=getchar();
12     while(ch>'9'||ch<'0')
13     {
14         if(ch=='-')
15             w=-1;
16         ch=getchar(); 
17     }
18     while(ch>='0'&&ch<='9')
19     {
20         x=(x<<3)+(x<<1)+ch-'0';
21         ch=getchar();
22     } 
23     x*=w;
24 } 
25 void input()
26 {
27     freopen("input.txt","r",stdin);
28 }
29 void dv(int x)
30 {
31     tot=0;
32     while(x)
33     {
34         e[++tot]=x%10;
35         x/=10;
36     }
37     e[tot+1]=0;
38 }
39 long long dfs(int pos,bool limit,bool zero,int pre)
40 {
41     if(pos==0)
42     {
43         if(zero&&!pre)
44             return 1;
45         else
46             return 0;
47     }
48     if(!limit&&~c[pos][pre])
49         return c[pos][pre];
50     int up=limit?e[pos]:9;
51     long long ans=0;
52     for(int i=0;i<=up;++i)
53         ans+=dfs(pos-1,limit&&(i==up),zero||i,(pre+i)%mod);
54     if(!limit&&zero)
55         c[pos][pre]=ans;
56     return ans;    
57 }
58 long long solve(int x)
59 {
60     dv(x);
61     memset(c,-1,sizeof(c));
62     return dfs(tot,1,0,0);
63 } 
64 int main()
65 {
66     input();
67     while(scanf("%d%d%d",&a,&b,&mod)==3)
68         printf("%lld
",solve(b)-solve(a-1));
69     return 0;
70 }

2 取模数