fork download
copy 
  1. #include <iostream>
  2. #include <bits/stdc++.h> 
  3. typedef long long ll;
  4.  
  5. using namespace std;
  6. string k; 
  7. int d; 
  8. int n; 
  9. ll M = 1e9 + 7; 
  10. const int N = 1e4 + 5; 
  11. const int D = 105; 
  12. ll dp[N][D][2][2]; 
  13. ll solve(int i, int sum, int can, int zer){
  14.  
  15.      if(i < 0 && !zer && sum == 0) return 1ll; 
  16.      else if(i < 0) return 0; 
  17.   if(~dp[i][sum][can][zer] && can) return dp[i][sum][can][zer] ; 
  18.      int j = n - 1 - i; 
  19.      ll ans = 0ll; 
  20.      int a = k[j] - '0'; 
  21.  for(int dig = 0; dig <= ((can)?9:a) ; dig++){
  22.  
  23.  
  24.  ans = (ans + 
  25.   solve(i- 1, (sum + dig)%d, (can||(dig < a)), (zer&&(dig == 0)) ))%M; 
  26.  
  27.    }
  28.    return dp[i][sum][can][zer] = ans; 
  29. }
  30.  
  31. int main() {
  32. 	ios_base::sync_with_stdio(false); 
  33.     cin.tie(NULL); cout.tie(NULL); 
  34.  
  35.     cin>>k; 
  36.     cin>>d; 
  37.     memset(dp, - 1, sizeof(dp)); 
  38.     n = k.length(); 
  39.     cout<<solve(n - 1, 0,0,1); 
  40.  
  41. }
Success #stdin #stdout 0.01s 36332KB
comments (?)
stdin
copy 
98765432109876543210
58
stdout
copy 
635270834
https://ideone.com/236BuB
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!