fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define _nhatminh  int main()
  3. #define ll long long
  4. #define str string
  5. #define fir first
  6. #define sec second
  7. #define ld long double
  8. #define pb push_back
  9. const ll MOD = 1e9+7;
  10. #define freopen(name) if(fopen(name".INP","r")) {freopen (name".INP","r",stdin); freopen (name".OUT","w",stdout);}
  11. #define ALL(x) (x).begin(),(x).end()
  12. #define piint pair < int , int >
  13. #define piL pair < int , ll>
  14. #define pLL pair < ll , ll >
  15. #define TIME (1.0*clock()/CLOCKS_PER_SEC)
  16. using namespace std;
  17. const int Max_n=1e5 ;
  18. str s ; 
  19. //int x ; 
  20. ll dp[10005][103][2];
  21. int k ; 
  22. void solve(){
  23. 	cin >> s ;
  24. 	cin >> k ;
  25. 	dp[0][0][0] = 1 ;
  26. 	int low = 0, high ;
  27. 	for (int i = 0 ; i < s.size() ; i ++ ){
  28. 		for (int m_k= 0 ; m_k < k ; m_k ++ ){
  29. 			for (int check = 0 ; check <= 1 ; check ++ ){
  30.  
  31. 				if (!check) high = s[i] -'0';
  32. 				else high = 9 ;
  33.  
  34. 				for (int DI = low ; DI <= high ; DI ++ ){
  35. 					if (check||DI<(s[i]-'0')){
  36. 						dp[i+1][(m_k+DI)%k][1] += dp[i][(m_k)][check]%MOD;
  37. 						dp[i+1][(m_k+DI)%k][1] %=MOD;
  38. 					}
  39. 					else {
  40. 						dp[i+1][(m_k+DI)%k][0] += (dp[i][(m_k)][check])%MOD;
  41. 						dp[i+1][(m_k+DI)%k][0] %=MOD;
  42. 					}
  43. 				}
  44. 			}
  45. 		}
  46. 	}
  47. 	ll ans =(dp[s.size()][0][1] +dp[s.size()][0][0]-1)%MOD;
  48. 	cout << ans << '\n';
  49. }
  50. _nhatminh{
  51. freopen("");
  52. ios_base::sync_with_stdio(0);
  53. cin.tie(0); cout.tie(0);
  54. int q=1;
  55. //cin >> q;
  56. while (q--)
  57. 	solve();
  58. cerr << '\n' << "Time elapsed " << TIME << "s.\n";
  59. return (0);
  60. }
Success #stdin #stdout #stderr 0.01s 5272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
stderr
copy 
Time elapsed 0.007771s.
https://ideone.com/Ge5lKK
language:
C++14 (gcc 8.3)
created:
2 days 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!