fork download 
  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][N][2][2]; 
  12.  
  13. ll solve(int i, int sum, int nz, int pos, int ucan, int lcan ){
  14.  
  15.      if(i < 0 && sum == 0) return 1ll; 
  16.      else if(i < 0) return 0ll; 
  17.  
  18.      if(~dp[i][sum][nz][pos] && ucan && lcan) return dp[i][sum][nz][pos]; 
  19.  
  20.      int ub = b[m - 1 - i] - '0'; 
  21.      int lb  = a[m - 1 - i] - '0'; 
  22.      cout<<ub<<" "<<lb<<endl; 
  23.      int kub = (ucan)? 9: ub; int klb = (lcan)?0:lb; 
  24.     cout<<"& we have: "<<kub<<" "<<klb<<endl;
  25.      ll ans = 0ll; 
  26.  
  27.     for(int dig = klb; dig <= kub; dig++){
  28.         int zer = (nz && (dig == 0)); 
  29.         int ns = (sum*10 + dig)%m; 
  30.          cout<<dig<<" -> "<<ns<<endl;
  31.         if(zer) ans = (ans + solve(i - 1,ns, zer, pos, ucan||(dig < ub), lcan||(dig>lb)) )%M; 
  32.         else{
  33.              if(pos && dig != d)
  34.       ans = (ans + solve(i-1,ns,zer,pos^1,ucan||(dig < ub), lcan||(dig>lb)))%M; 
  35.              else if(!pos && dig == d) 
  36. ans = (ans + solve(i-1,ns,zer,pos^1,ucan||(dig < ub), lcan||(dig>lb)))%M; 
  37.          }
  38.     }
  39.     if(ucan && lcan) return dp[i][sum][nz][pos]= ans; 
  40.     else return ans; 
  41. }
  42.  
  43. int main() {
  44. 	ios_base::sync_with_stdio(false); 
  45.     cin.tie(NULL); cout.tie(NULL); 
  46.     memset(dp, - 1, sizeof(dp)); 
  47.     cin>>m>>d; 
  48.     cin>>a>>b; 
  49.    cout<<solve(m - 1, 0,1,1,0,0)<<"\n"; 
  50.  
  51. }
Success #stdin #stdout 0.02s 129168KB
comments (?)
stdin 
2 0
1
9
stdout 
9 1
& we have: 9 1
1 -> 1
-48 -48
& we have: 9 -48
-48 -> 0
-47 -> -1
-46 -> 0
-45 -> -1
-44 -> 0
-43 -> -1
-42 -> 0
-41 -> -1
-40 -> 0
-39 -> -1
-38 -> 0
-37 -> -1
-36 -> 0
-35 -> -1
-34 -> 0
-33 -> -1
-32 -> 0
-31 -> -1
-30 -> 0
-29 -> -1
-28 -> 0
-27 -> -1
-26 -> 0
-25 -> -1
-24 -> 0
-23 -> -1
-22 -> 0
-21 -> -1
-20 -> 0
-19 -> -1
-18 -> 0
-17 -> -1
-16 -> 0
-15 -> -1
-14 -> 0
-13 -> -1
-12 -> 0
-11 -> -1
-10 -> 0
-9 -> 1
-8 -> 0
-7 -> 1
-6 -> 0
-5 -> 1
-4 -> 0
-3 -> 1
-2 -> 0
-1 -> 1
0 -> 0
1 -> 1
2 -> 0
3 -> 1
4 -> 0
5 -> 1
6 -> 0
7 -> 1
8 -> 0
9 -> 1
2 -> 0
-48 -48
& we have: 9 0
0 -> 0
1 -> 1
2 -> 0
3 -> 1
4 -> 0
5 -> 1
6 -> 0
7 -> 1
8 -> 0
9 -> 1
3 -> 1
-48 -48
& we have: 9 0
0 -> 0
1 -> 1
2 -> 0
3 -> 1
4 -> 0
5 -> 1
6 -> 0
7 -> 1
8 -> 0
9 -> 1
4 -> 0
5 -> 1
6 -> 0
7 -> 1
8 -> 0
9 -> 1
-48 -48
& we have: -48 0
8
https://ideone.com/bRIkpt
language:
C++ (gcc 8.3)
created:
2 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!