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. int n; 
  9. ll M = 1e9 + 7; 
  10. const int N = 2e3 + 5; 
  11.  
  12. ll dp[N][N][2][2]; 
  13.  
  14. ll solve(int i, int sum, int nz, int pos, int ucan, int lcan ){
  15.  
  16.      if(i < 0 && sum == 0) return 1ll; 
  17.      else if(i < 0) return 0ll; 
  18.  
  19.      if(~dp[i][sum][nz][pos] && ucan && lcan) return dp[i][sum][nz][pos]; 
  20.      int ub = b[n - 1 - i] - '0'; 
  21.      int lb  = a[n - 1 - i] - '0'; 
  22.      int kub = (ucan)? 9: ub; int klb = (lcan)?0:lb; 
  23.      ll ans = 0ll; 
  24.  
  25.     for(int dig = klb; dig <= kub; dig++){
  26.         int zer = (nz && (dig == 0)); 
  27.         int ns = (sum*10 + dig)%m; 
  28.         if(zer) ans = (ans + solve(i - 1,ns, zer, pos, ucan||(dig < ub), lcan||(dig>lb)) )%M; 
  29.         else{
  30.              if(pos && dig != d)
  31.       ans = (ans + solve(i-1,ns,zer,pos^1,ucan||(dig < ub), lcan||(dig>lb)))%M; 
  32.              else if(!pos && dig == d) 
  33. ans = (ans + solve(i-1,ns,zer,pos^1,ucan||(dig < ub), lcan||(dig>lb)))%M; 
  34.          }
  35.     }
  36.     if(ucan && lcan) return dp[i][sum][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.     n = a.size(); 
  47.    cout<<solve(n - 1, 0,1,1,0,0)<<"\n"; 
  48.  
  49. }
Success #stdin #stdout 0.02s 129180KB
comments (?)
stdin
copy 
19 7
1000
9999
stdout
copy 
6
https://ideone.com/QNm9Ak
language:
C++ (gcc 8.3)
created:
4 hours 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!