luogu 3413 SAC#1 - 萌数

                 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6usingnamespace std;
 7 typedef longlong lol;
 8 lol f[1001][12][12][2],Mod=1e9+7;
 9char s1[1001],s2[1001],s[1001];
10 lol dfs(int pos,int pre,int bef,int t,int k,int flag)
11 {int i;
12if (pos<0) return t;
13if (!flag&&f[pos][pre+1][bef+1][t]!=-1) return f[pos][pre+1][bef+1][t];
14int end;
15   lol cnt=0;
16if (flag) end=s[pos]-‘0‘;
17else end=9;
18for (i=0;i<=end;i++)
19    {
20       cnt+=dfs(pos-1,i,k?pre:-1,t||((i==pre)&&k)||((i==bef)&&k),k||(i!=0),flag&&(i==end));
21       cnt%=Mod;
22    }
23if (!flag&&k&&bef!=-1) f[pos][pre+1][bef+1][t]=cnt;
24return cnt;
25}
26 lol solve(char ch[])
27 {int i;
28   memset(f,-1,sizeof(f));
29int len=strlen(ch);
30for (i=0;i<len;i++)
31     s[len-i-1]=ch[i];
32while (s[len-1]==‘0‘) len--;
33return dfs(len-1,-1,-1,0,0,1);
34}
35int main()
36 {int i;
37   cin>>s1>>s2;
38int len=strlen(s1);
39   s1[len-1]--;
40for (i=len-1;i>=0;i--)
41if (s1[i]<‘0‘) s1[i]+=10,s1[i-1]--;
42   printf("%lld\n",(solve(s2)-solve(s1)+Mod)%Mod);
43 }