fork download
copy 
  1. #include <bits/stdc++.h> 
  2. using namespace std;  
  3.  
  4. typedef long long ll;  
  5. typedef pair<int, int> ii;  
  6.  
  7. const int INF = 1e9;  
  8. const ll LINF = 1e18;  
  9.  
  10. const int MOD = 1e9 + 7; 
  11. const int MX = 2e3; 
  12. const int M = 2e3; 
  13.  
  14. void add(int& a, int b) {
  15. 	a += b; 
  16. 	if (a >= MOD) a -= MOD; 
  17. }
  18.  
  19. int m, d; 
  20. int memo[MX][2][2][2][2][M]; 
  21. string a, b; 
  22. vector<int> digit_a, digit_b; 
  23.  
  24. // larger là phần prefix ở trước vị trí idx đã lớn hơn số a hay chưa
  25. // even = 0/1: hiện tại đang ở vị trí lẻ hay chẵn
  26. // Lưu ý các vị trí là leading zeros thì vô nghĩa
  27. int dp(int idx, bool leading, bool larger, bool smaller, bool even, int r) {
  28. 	if (idx == -1) return (r == 0);  
  29.  
  30. 	int& ans = memo[idx][leading][larger][smaller][even][r]; 
  31. 	if (ans != -1) return ans;   
  32.  
  33. 	ans = 0;    
  34. 	int min_digit = (larger) ? 0 : digit_a[idx]; 
  35. 	int max_digit = (smaller) ? 9 : digit_b[idx]; 
  36.  
  37. 	for (int i = min_digit; i <= max_digit; i++) {
  38. 		bool new_leading = leading & (i == 0); 
  39. 		bool valid = true; 
  40. 		if (!new_leading) {
  41. 			if ((even && i != d) || (!even && i == d)) valid = false; 
  42. 		}
  43. 		if (!valid) continue; 
  44. 		add(ans, dp(idx - 1, new_leading, larger | (i > digit_a[idx]), smaller | (i < digit_b[idx]), 
  45. 			        even ^ (!new_leading), (r * 10 + i) % m)); 
  46. 	}
  47.  
  48. 	return ans; 
  49. }
  50.  
  51. int main() {
  52. 	ios::sync_with_stdio(0); cin.tie(0);  	
  53. 	cin >> m >> d; 
  54. 	cin >> a; 
  55. 	cin >> b; 
  56.  
  57. 	reverse(a.begin(), a.end()); 
  58. 	reverse(b.begin(), b.end());   
  59. 	for (int i = 0; i < a.size(); i++) digit_a.push_back(a[i] - '0');   
  60. 	for (int i = 0; i < b.size(); i++) digit_b.push_back(b[i] - '0');  
  61. 	while (digit_a.size() < digit_b.size()) digit_a.push_back(0);  
  62.  
  63. 	memset(memo, -1, sizeof memo);   
  64.  
  65. 	cout << dp(digit_b.size() - 1, 1, 0, 0, 0, 0) << '\n'; 
  66. }
Success #stdin #stdout 0.04s 253612KB
comments (?)
stdin
copy 
2 6
10
99
stdout
copy 
8
https://ideone.com/d9Yv6f
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!