fork download
copy 
  1. #include<iostream>
  2. #include<string>
  3. #include<algorithm>
  4. #include<cstring>
  5. using namespace std;
  6.  
  7. #define MAX_A 50
  8. #define MAX_C 750
  9. #define MAX_D 50
  10. #define r(A) A.begin(),A.end()
  11. #define sz(x) (int)(x).size()
  12.  
  13. int dp[MAX_A][MAX_D][MAX_C][2];
  14. int f[MAX_A];
  15. int c, d, n;
  16.  
  17. string a, b, s, rs;
  18.  
  19. string dec(string a) {
  20. 	for (int i = sz(a) - 1;; --i) {
  21. 		if (a[i] == '0') a[i] = '9';
  22. 		else { a[i]--; break; }
  23.  
  24. 	}
  25. 	if (sz(a) > 1 && a[0] == '0') return a.substr(1);
  26. 	return a;
  27. }
  28.  
  29. int calc(string a) {
  30. 	memset(dp, 0, sizeof(dp));
  31. 	memset(f, 0, sizeof(f));
  32. 	dp[0][0][0][0] = 1;
  33. 	n = a.size() / 2;
  34. 	s = a.substr(0, n);
  35. 	rs = a.substr(n);
  36. 	reverse(r(s));
  37. 	if (s < rs) {
  38. 		reverse(r(s));
  39. 		dec(s);
  40. 	}
  41. 	else {
  42. 		reverse(r(s));
  43. 	}
  44. 	int z = 1;
  45. 	for (int i = 0; i < n; i++) {
  46. 		f[i] += z;
  47. 		z = z * 10 % c;
  48. 	}
  49. 	for (int i = 0; i < n; i++) {
  50. 		f[n - 1 - i] += z;
  51. 		z = z * 10 % c;
  52. 	}
  53. 	for (int i = 0; i < n; i++) {
  54. 		for (int j = 0; j < c; j++) {
  55. 			for (int k = 0; k <= d; k++) {
  56. 				for (int l = 0; l < 2; l++) {
  57. 					for (int m = 0; m < 10; m++) {
  58. 						int I = i + 1, J = (j + f[i] * m) % c, K = k + m, L = l;
  59. 						if (m < s[i] - '0') L = 1;
  60. 						if (!l && m > s[i] - '0') continue;
  61. 						dp[I][J][K][L] += dp[i][j][k][l];
  62. 						dp[I][J][K][L] = (dp[I][J][K][L] + 1000000) % 10000;
  63. 					}
  64. 				}
  65. 			}
  66. 		}
  67. 	}
  68. 	int sum = 0;
  69. 	for (int i = 0; i <= d; i++) {
  70. 		for (int j = 0; j < 2; j++) {
  71. 			if (i * 2 == d) {
  72. 				sum += dp[n][0][i][j];
  73. 				sum %= 10000;
  74. 			}
  75. 		}
  76. 	}
  77. 	return sum;
  78. }
  79.  
  80.  
  81. int main() {
  82. 	cin >> a >> b >> c >> d;
  83. 	cout << (calc(b) - calc(a) + 1000000) % 10000 << endl;
  84. 	return 0;
  85. }
Success #stdin #stdout 0.03s 18072KB
comments (?)
stdin
copy 
1000000001 9999999999 49 50
stdout
copy 
109
https://ideone.com/EL5lIo
language:
C++14 (gcc 8.3)
created:
8 years 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!