fork download
copy 
  1. #include <iostream>
  2. #include <bits/stdc++.h> 
  3. typedef long long ll;
  4.  
  5. using namespace std;
  6. string a,b; 
  7. int m, d; 
  8. ll M = 1e9 + 7; 
  9. const int N = 2e3 + 5; 
  10.  
  11. ll dp[N][2][2]; 
  12.  
  13. ll solve(int i, int nz, int pos, int ucan, int lcan ){
  14.  
  15.      if(i < 0) return 1ll; 
  16.  
  17.      if(~dp[i][nz][pos] && ucan && lcan) return dp[i][nz][pos]; 
  18.  
  19.      int ub = b[m - 1 - i] - '0'; 
  20.      int lb  = a[m - 1 - i] - '0'; 
  21.      int kub = (ucan)? 9: ub; int klb = (lcan)?0:lb; 
  22.      ll ans = 0ll; 
  23.       cout<<i<<endl; 
  24.      cout<<ub<<" "<<kub<<endl; 
  25.      cout<<lb<<" "<<klb<<endl;
  26.     for(int dig = klb; dig <= kub; dig++){
  27.         int zer = (nz && (dig == 0)); 
  28.         if(zer) ans = (ans + solve(i - 1,zer, pos, ucan||(dig < ub), lcan||(dig>lb)) )%M; 
  29.         else{
  30.              if(pos && dig != d)
  31.       ans = (ans + solve(i-1,zer,pos^1,ucan||(dig < ub), lcan||(dig>lb)))%M; 
  32.              else if(dig == d) 
  33. ans = (ans + solve(i-1,zer,pos^1,ucan||(dig < ub), lcan||(dig>lb)))%M; 
  34.          }
  35.     }
  36.     if(ucan && lcan) return dp[i][nz][pos]= ans; 
  37.     else return ans; 
  38. }
  39.  
  40. int main() {
  41. 	ios_base::sync_with_stdio(false); 
  42.     cin.tie(NULL); cout.tie(NULL); 
  43.     memset(dp, - 1, sizeof(dp)); 
  44.     cin>>m>>d; 
  45.     cin>>a>>b; 
  46.    cout<<solve(m - 1, 1,1,0,0)<<"\n"; 
  47.  
  48. }
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
2 6
10
99
stdout
copy 
1
9 9
1 1
0
9 9
0 0
0
9 9
0 0
0
9 9
0 0
9
https://ideone.com/FVWwGV
language:
C++ (gcc 8.3)
created:
1 hour ago
visibility:
public

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!