fork(10) download
  1. // Ancient Prophecy (D), by Errichto
  2. // AC, O(n^2)
  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. const int inf = 1e9 + 120;
  12.  
  13. int t[nax];
  14. char sl[nax];
  15. // int dp[nax][nax];
  16. // pref[a][b] = sum(dp[1..a][b])
  17. int pref[nax][nax];
  18. int nxt[nax][nax];
  19.  
  20. int cmp(int i, int j) {
  21. if(t[i] < t[j]) return -1;
  22. if(t[i] > t[j]) return 1;
  23. return 0;
  24. }
  25.  
  26. int dp(int a, int b) {
  27. int x = pref[a][b] - pref[a-1][b];
  28. if(x < 0) x += mod;
  29. return x;
  30. }
  31.  
  32. int main() {
  33. int n;
  34. scanf("%d", &n);
  35. scanf("%s", sl);
  36. RI(i, n) t[i] = sl[i-1] - '0';
  37.  
  38. for(int a = n; a >= 1; --a)
  39. for(int b = n; b > a; --b) {
  40. int & x = nxt[a][b];
  41. if(t[a] != t[b]) x = a;
  42. else if(b == n) x = inf;
  43. else x = nxt[a+1][b+1];
  44. }
  45.  
  46. RI(i, n) {
  47. // dp[1][i] = 1;
  48. RI(j, n) pref[j][i] = 1;
  49. }
  50. FOR(c, 2, n) FOR(d, c, n) {
  51. int & x = pref[c][d];
  52. int b = c - 1;
  53. int a = b - (d - c);
  54. x = pref[b][b] - pref[max(a,0)][b];
  55. if(x < 0) x += mod;
  56. if(a >= 1) {
  57. int where = nxt[a][c];
  58. if(where < c && t[where] < t[c+where-a]) {
  59. x += dp(a, b);
  60. if(x >= mod) x -= mod;
  61. }
  62. }
  63. if(t[c] == 0) x = 0;
  64. pref[c][d] = x + pref[c-1][d];
  65. if(pref[c][d] >= mod) pref[c][d] -= mod;
  66. }
  67. int ans = 0;
  68. RI(i, n) ans = (ans + dp(i, n)) % mod;
  69. printf("%d\n", ans);
  70. return 0;
  71. }
Runtime error #stdin #stdout 0s 199168KB
stdin
Standard input is empty
stdout
Standard output is empty