fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. const int N = 20;
  6. const int mod = 1000000007;
  7.  
  8. ll dp[N][2][N][N][N][10];
  9. ll dp1[N][N][N][N][10];
  10. int vis[N][2][N][N][N][10];
  11. int cs;
  12. ll digit[N][10];
  13. vector<int>vc;
  14.  
  15. ll rec(int pos,int sm,int smd,int bgd,int p,int d)
  16. {
  17.     if(smd>p || 18-bgd<p) return 0;
  18.     if(pos==19)
  19.     {
  20.         if(smd>p) return 0;
  21.         if(18-bgd>=p) return 1;
  22.         return 0;
  23.     }
  24.     if(sm==1 && dp1[pos][smd][bgd][p][d]!=-1) return dp1[pos][smd][bgd][p][d];
  25.     ll &ret=dp[pos][sm][smd][bgd][p][d];
  26.     if(vis[pos][sm][smd][bgd][p][d]==cs) return ret;
  27.     vis[pos][sm][smd][bgd][p][d]=cs;
  28.     ret=0;
  29.     if(sm==1)
  30.     {
  31.         ret+=rec(pos+1,sm,smd,bgd,p,d);
  32.         ret+=1LL*d*rec(pos+1,sm,smd+1,bgd,p,d);
  33.         ret+=1LL*(9-d)*rec(pos+1,sm,smd,bgd+1,p,d);
  34.     }
  35.     else
  36.     {
  37.         for(int i=0; i<=9; i++)
  38.         {
  39.             if(sm==0 && i>vc[pos]) break;
  40.             ret+=rec(pos+1,sm|(i<vc[pos]),smd+(i<d),bgd+(i>d),p,d);
  41.         }
  42.     }
  43.     if(sm==1) dp1[pos][smd][bgd][p][d]=ret;
  44.     return ret;
  45. }
  46.  
  47. ll cal(ll x,int p,int d)
  48. {
  49.     vc.clear();
  50.     while(x>0)
  51.     {
  52.         vc.push_back(x%10);
  53.         x/=10;
  54.     }
  55.     while(vc.size()<19) vc.push_back(0);
  56.     reverse(vc.begin(),vc.end());
  57.     return rec(0,0,0,0,p,d);
  58. }
  59.  
  60.  
  61.  
  62. int main()
  63. {
  64.     memset(dp1,-1,sizeof dp1);
  65.     int t;
  66.     ll L,R;
  67.     scanf("%d",&t);
  68.     while(t--)
  69.     {
  70.         scanf("%lld %lld",&L,&R);
  71.         cs++;
  72.         memset(digit,0,sizeof digit);
  73.         for(int p=0; p<=18; p++)
  74.         {
  75.             for(int d=0; d<=9; d++)
  76.             {
  77.                 digit[p][d]=cal(R,p,d);
  78.             }
  79.         }
  80.         cs++;
  81.         for(int p=0; p<=18; p++)
  82.         {
  83.             for(int d=0; d<=9; d++)
  84.             {
  85.                 digit[p][d]-=cal(L-1,p,d);
  86.                 digit[p][d]%=mod;
  87.             }
  88.         }
  89.         ll ans=0;
  90.         for(int p=0; p<=18; p++)
  91.         {
  92.             for(int d1=0; d1<=9; d1++)
  93.             {
  94.                 for(int d2=d1+1; d2<=9; d2++)
  95.                 {
  96.                     ll tmp=1LL*(d2-d1)*digit[p][d1];
  97.                     tmp%=mod;
  98.                     tmp=1LL*tmp*digit[p][d2];
  99.                     tmp%=mod;
  100.                     ans+=2LL*tmp;
  101.                     ans%=mod;
  102.                 }
  103.             }
  104.         }
  105.         printf("%lld\n",ans);
  106.     }
  107.  
  108. }
Success #stdin #stdout 0s 16276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/E1Kmxi
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!