fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
  6. #define        FOR(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
  7. #define       FORD(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
  8. #define          file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
  9.  
  10. // end of template
  11.  
  12. const int MAX_LR = 202;
  13. const int MAX_X = 22;
  14. const int MAX_K = 1e4 + 4;
  15. const int MOD = 1e9 + 7;
  16.  
  17. string L, R, X;
  18. int K, v[MAX_X], kmp[MAX_X], nxt[MAX_X][10];
  19.  
  20. void init(void) {
  21. 	cin >> L >> R >> X >> K;
  22. 	REP(i, X.size()) cin >> v[i + 1];
  23. }
  24.  
  25. void add(int &a, int b) {
  26. 	a += b;
  27. 	if (a >= MOD) a -= MOD;
  28. }
  29.  
  30. int dp[MAX_LR][MAX_X][MAX_K][2];
  31.  
  32. int solve(const string &R) {
  33. 	memset(dp, 0, sizeof(dp));
  34. 	dp[0][0][0][0] = 1;
  35. 	REP(i, R.size()) REP(suff, X.size() + 1) REP(beauty, K + 1) REP(less_r, 2) if (dp[i][suff][beauty][less_r]) {
  36. 		REP(digit, less_r ? 10 : R[i] - '0' + 1) {
  37. 			int new_suff = nxt[suff][digit];
  38. 			int new_beauty = beauty + v[new_suff];
  39. 			int new_less_r = less_r || digit < R[i] - '0';
  40. 			if (new_beauty <= K) add(dp[i + 1][new_suff][new_beauty][new_less_r], dp[i][suff][beauty][less_r]);
  41. 		}
  42. 	}
  43. 	int res = 0;
  44. 	REP(suff, X.size() + 1) REP(beauty, K + 1) REP(less_r, 2) add(res, dp[R.size()][suff][beauty][less_r]);
  45. 	return res;
  46. }
  47.  
  48. void process(void) {
  49. 	kmp[0] = 0;
  50. 	nxt[0][X[0] - '0'] = 1;
  51. 	FOR(i, 1, X.size()) {
  52. 		kmp[i] = i == 1 ? 0 : nxt[kmp[i - 1]][X[i - 1] - '0'];
  53. 		v[i] += v[kmp[i]];
  54. 		REP(j, 10) nxt[i][j] = j == X[i] - '0' ? i + 1 : nxt[kmp[i]][j];
  55. 	}
  56. 	FORD(i, (int) L.size() - 1, 0) {
  57. 		--L[i];
  58. 		if (L[i] < '0') L[i] += 10;
  59. 		else break;
  60. 	}
  61. 	cout << (solve(R) - solve(L) + MOD) % MOD << '\n';
  62. }
  63.  
  64. int main(void) {
  65. 	ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr);
  66. 	file("badnum");
  67. 	init();
  68. 	process();
  69. 	return (0^0);
  70. }
Success #stdin #stdout 0.14s 350928KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/OTIzZ2
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!