luogu2602 [ZJOI2010]数字计数两解

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=1e6+5;
 4 long long a,b;
 5 long long ansa[15],ansb[15];
 6 int tot,e[15];
 7 long long c[15],d[15];
 8 template<class t>void red(t &x)
 9 {
10     int w=1;
11     x=0;
12     char ch=getchar();
13     while(ch>'9'||ch<'0')
14     {
15         if(ch=='-')
16             w=-1;
17         ch=getchar();
18     }
19     while(ch>='0'&&ch<='9')
20     {
21         x=(x<<3)+(x<<1)+ch-'0';
22         ch=getchar();
23     }
24     x*=w;
25 }
26 void input()
27 {
28     freopen("input.txt","r",stdin);
29     //freopen("output.txt","w",stdout);
30 }
31 void read()
32 {
33     red(a);
34     red(b);    
35 }
36 void dv(long long x)
37 {
38     tot=0;
39     while(x!=0)
40     {
41         e[++tot]=x%10;
42         x/=10;
43     }    
44 } 
45 void solve()
46 {
47     dv(a-1);
48     for(int i=tot;i>=1;--i)
49     {
50         for(int j=0;j<=9;++j)
51             ansa[j]+=c[i-1]*e[i];
52         for(int j=0;j<e[i];++j)
53             ansa[j]+=d[i-1];
54         long long t=0;
55         for(int j=i-1;j>=1;--j)
56             t=t*10+e[j];
57         ansa[e[i]]+=t+1;
58         ansa[0]-=d[i-1];    
59     }
60     dv(b);
61     for(int i=tot;i>=1;--i)
62     {
63         for(int j=0;j<=9;++j)
64             ansb[j]+=c[i-1]*e[i];
65         for(int j=0;j<e[i];++j)
66             ansb[j]+=d[i-1];
67         long long t=0;
68         for(int j=i-1;j>=1;--j)
69             t=t*10+e[j];
70         ansb[e[i]]+=t+1;
71         ansb[0]-=d[i-1];
72     }
73 }
74 void work()
75 {
76     d[0]=1;
77     for(int i=1;i<=13;++i)
78     {
79         c[i]=c[i-1]*10+d[i-1];
80         d[i]=d[i-1]*10;
81     }
82     solve();
83     for(int i=0;i<=9;++i)
84         printf("%lld ",ansb[i]-ansa[i]);
85 }
86 int main()
87 {
88     //input();
89     read();
90     work(); 
91     return 0;
92 }

递推

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=1e3+5;
 4 const int mod=1e9+7;
 5 int n,m,mark;
 6 char l[maxn],r[maxn];
 7 int numl,numr;
 8 int tot,e[maxn];
 9 long long c[maxn][20][2];
10 template<class t>void red(t &x)
11 {
12     int w=1;
13     x=0;
14     char ch=getchar();
15     while(ch>'9'||ch<'0')
16     {
17         if(ch=='-')
18             w=-1;
19         ch=getchar(); 
20     }
21     while(ch>='0'&&ch<='9')
22     {
23         x=(x<<3)+(x<<1)+ch-'0';
24         ch=getchar();
25     } 
26     x*=w;
27 } 
28 void input()
29 {
30     freopen("input.txt","r",stdin);
31 }
32 void dv(int x)
33 {
34     tot=0;
35     while(x)
36     {
37         e[++tot]=x%10;
38         x/=10;
39     }
40     e[tot+1]=0;
41 } 
42 long long dfs(int pos,bool limit,bool zero,int pre,int qpre,bool dc)
43 {
44     if(pos==0)
45         return dc;
46     if(!limit&&c[pos][pre][dc]!=-1)
47         return c[pos][pre][dc];
48     int up=limit?e[pos]:9;
49     long long ans=0;
50     for(int i=0;i<=up;++i)
51         ans+=dfs(pos-1,limit&&(i==up),zero||i,i,zero?pre:-1,dc||(i==pre&&zero)||(i==qpre&&zero))%mod;
52     if(!limit&&zero&&qpre!=-1)
53         c[pos][pre][dc]=ans;
54     return ans;
55 }
56 long long solve()
57 {
58     //dv(x);
59     tot=0;
60     while(m--)
61         e[++tot]=r[m]-'0';
62     while(!e[tot])
63         --tot; 
64     memset(c,-1,sizeof(c));
65     long long ans=dfs(tot,1,0,-1,-1,0)%mod; 
66     tot=0;
67     while(n--)
68         e[++tot]=l[n]-'0';
69     while(!e[tot])
70         --tot;
71     memset(c,-1,sizeof(c));
72     ans-=dfs(tot,1,0,-1,-1,0)%mod;
73     return ans;
74 }
75 void read()
76 {
77     scanf("%s%s",l,r);
78     n=strlen(l);
79     m=strlen(r);
80 }
81 void work()
82 {
83     int i=1;
84     while(l[n-i]=='0'&&n>i)
85     {
86         l[n-i]='9';
87         ++i;
88     }
89     l[n-i]-=1;
90     printf("%lld",(solve()+mod)%mod);
91 }
92 int main()
93 {
94     input();
95     read();
96     work();
97     return 0;
98 }

dfs

luogu2602 [ZJOI2010]数字计数 两解

luogu2602 [ZJOI2010]数字计数两解