fork download
copy 
  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <cstdio>
  4. #include <stdio.h>
  5. #include <cmath>
  6. #include <math.h>
  7. #include <map>
  8. #include <vector>
  9. #include <set>
  10. #include <string>
  11. #include <string.h>
  12. #include <cstring>
  13. #include <algorithm>
  14. #include <time.h>
  15. #include <ctime>
  16. #include <list>
  17. #include <fstream>
  18.  
  19. #define fname "1"
  20. #define pb push_back
  21. #define mp make_pair
  22. #define F first
  23. #define S second
  24. #define in scanf
  25. #define out printf
  26. #define y1 dasdasfasfas
  27. #define x1 wqdadfasfasfas
  28.  
  29. using namespace std;
  30.  
  31. typedef long long ll;
  32.  
  33. inline double Time() {return ((clock() * 1.0) / CLOCKS_PER_SEC);}
  34.  
  35. const int N = 100500, MOD = 1000000007, inf = 2000000000;
  36.  
  37. char CH[5100];
  38.  
  39. string S;
  40.  
  41. int n, d[5100][5100];
  42.  
  43. bool was[5100][5100];
  44.  
  45. ll h[5100], deg[5100];
  46.  
  47. const ll P = 2017ll, base = 1e18 + 7ll;
  48.  
  49. ll mod(ll x) {
  50. 	return ((x % base) + base) % base;
  51. }
  52.  
  53. ll mult(ll x, ll y, ll M) {
  54. 	if (x < y) {
  55. 		swap(x, y);
  56. 	}
  57. 	ll rec = 0ll;
  58. 	while (y) {
  59. 		if (y & 1) {
  60. 			y--;
  61. 			rec += x;
  62. 			rec = mod(rec);
  63. 		}
  64. 		else {
  65. 			x += x;
  66. 			x = mod(x);
  67. 			y /= 2ll;
  68. 		}
  69. 	}                   
  70. 	return rec;
  71. }
  72.  
  73. bool H(int l, int r, int L, int R) {
  74. 	return mod(h[r] - mult(h[l - 1], deg[r - l + 1], base)) == mod(h[R] - mult(h[L - 1], deg[R - L + 1], base));            
  75. }
  76.  
  77. bool check(int l, int r, int L, int R) {
  78. 	if (l < 1) {
  79. 		return 0;
  80. 	}
  81. 	int lt = 0;
  82. 	int rt = r - l;
  83. 	int rec = -1;
  84. 	while (lt <= rt) {
  85. 		int mid = ((lt + rt) / 2);
  86. 		if (H(l, l + mid, L, L + mid)) {
  87. 			lt = mid + 1;
  88. 		}
  89. 		else {
  90. 			rt = mid - 1;
  91. 			rec = mid;
  92. 		}                        
  93. 	}
  94. 	if (rec == -1 || S[l + rec - 1] > S[L + rec - 1]) {
  95. 		return 0;
  96. 	}
  97. 	return 1;
  98. }
  99.  
  100. int DP(int MAX, int cur, int done) {
  101. 	if (cur < 1 || MAX < 1 || S[cur - 1] == '0') {
  102. 		return 0ll;
  103. 	}
  104. 	if (was[MAX][cur]) {
  105. 		return d[MAX][cur];
  106. 	}
  107. 	was[MAX][cur] = 1;
  108. 	if (cur == 1) {
  109. 		return d[MAX][cur] = 1;
  110. 	}
  111. 	for (int er = 1; er < MAX; er++) {
  112. 		d[MAX][cur] += DP(er, cur - er, cur - 1);
  113. 		while (d[MAX][cur] >= MOD) {
  114. 			d[MAX][cur] -= MOD;
  115. 		}
  116. 	}
  117. 	if (check(cur - MAX, cur - 1, cur, done)) {
  118. 		d[MAX][cur] += DP(MAX, cur - MAX, cur - 1);
  119. 		while (d[MAX][cur] >= MOD) {
  120. 			d[MAX][cur] -= MOD;
  121. 		}
  122. 	}
  123. 	return d[MAX][cur];
  124. }
  125.  
  126. int main() {
  127.  
  128.    srand(time(NULL));
  129.    #ifndef ONLINE_JUDGE
  130.    	freopen(".in", "r", stdin);
  131.    	freopen(fname".out", "w", stdout);
  132.    #endif
  133.    scanf("%d\n%s", &n, CH);
  134.    S = CH;
  135.    deg[0] = 1ll;
  136.    for (int i = 1; i <= n; i++) {
  137.    	deg[i] = mult(deg[i - 1], P, base);
  138.    	h[i] = mult((h[i - 1] + ll(S[i - 1])), P, base);
  139.    }
  140.    int answer = 0;
  141.    for (int i = 1; i <= n; i++) {
  142.    	answer += DP(i, n - i + 1, n);
  143.    	while (answer >= MOD) {
  144.    		answer -= MOD;
  145.    	}        
  146.    }
  147.    printf("%d", answer);
  148.    return 0;
  149. }
  150.  
Success #stdin #stdout 0s 130560KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/grWuOb
language:
C++ (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!