fork download
  1. // Ancient Prophecy (D), by Errichto
  2. // AC, O(n^2 log(n)), hash and binary search
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5. #define FOR(i,a,b) for(int i = (a); i <= (b); ++i)
  6. #define RI(i,n) FOR(i,1,(n))
  7. #define REP(i,n) FOR(i,0,(n)-1)
  8.  
  9. const int nax = 5005;
  10. const int mod = 1e9 + 7;
  11.  
  12. int t[nax];
  13. char sl[nax];
  14. // int dp[nax][nax];
  15. // pref[a][b] = sum(dp[1..a][b])
  16. int pref[nax][nax];
  17. int h[nax][nax];
  18.  
  19. int cmp(int i, int j) {
  20. if(t[i] < t[j]) return -1;
  21. if(t[i] > t[j]) return 1;
  22. return 0;
  23. }
  24.  
  25. int cmp(int a, int b, int c, int d) {
  26. if(t[a] != t[c]) return cmp(a, c);
  27. if(h[a][b] == h[c][d]) return 0;
  28. int low = 0, high = b - a;
  29. while(low < high) {
  30. int x = (low + high) / 2;
  31. if(h[a][a+x] == h[c][c+x]) low = x + 1;
  32. else high = x;
  33. }
  34. assert(t[a+low] != t[c+low]);
  35. return cmp(a+low, c+low);
  36. }
  37.  
  38. int dp(int a, int b) {
  39. int x = pref[a][b] - pref[a-1][b];
  40. if(x < 0) x += mod;
  41. return x;
  42. }
  43.  
  44. int main() {
  45. int n;
  46. scanf("%d", &n);
  47. scanf("%s", sl);
  48. RI(i, n) t[i] = sl[i-1] - '0';
  49. RI(i, n) {
  50. h[i][i] = t[i];
  51. FOR(j, i+1, n)
  52. h[i][j] = (11LL * h[i][j-1] + t[j]) % mod;
  53. }
  54. RI(i, n) {
  55. // dp[1][i] = 1;
  56. RI(j, n) pref[j][i] = 1;
  57. }
  58. FOR(c, 2, n) FOR(d, c, n) {
  59. int & x = pref[c][d];
  60. int b = c - 1;
  61. int a = b - (d - c);
  62. x = pref[b][b] - pref[max(a,0)][b];
  63. if(x < 0) x += mod;
  64. if(a >= 1 && cmp(a,b,c,d) == -1) {
  65. x += dp(a, b);
  66. if(x >= mod) x -= mod;
  67. }
  68. if(t[c] == 0) x = 0;
  69. pref[c][d] = x + pref[c-1][d];
  70. if(pref[c][d] >= mod) pref[c][d] -= mod;
  71. }
  72. int ans = 0;
  73. RI(i, n) ans = (ans + dp(i, n)) % mod;
  74. printf("%d\n", ans);
  75. return 0;
  76. }
Runtime error #stdin #stdout 0s 199168KB
stdin
D
stdout
Standard output is empty