読者です 読者をやめる 読者になる 読者になる

Codeforces Good Bye 2015 D: New Year and Ancient Prophecy

kenkoooo.hatenablog.com

rng_58 さんのコードを参考にした。
よく考えたら、ハッシュなんか使わなくても解けるんだよなあ

#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <string.h>

using namespace std;
typedef signed long long ll;

#define ALL(a) (a.begin()), (a.end())
#define UNIQUE(a) a.erase(unique(a.begin(), a.end()), a.end())
const int MOD = (int)1e9 + 7;

int main() {
  int n;
  string str;
  cin >> n >> str;

  // dp[i][j]:=i文字目まで見て、最後の数字がj桁である組み合わせ
  vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
  // dp[i][j]:=i文字目まで見て、最後の数字がj桁以下である組み合わせ
  vector<vector<int>> dpSum(n + 1, vector<int>(n + 1, 0));
  // dist[i][j]:= str.substr(i,k)=str.substr(j,k)となる最大のk
  vector<vector<int>> dist(n + 1, vector<int>(n + 1, 0));

  for (int i = n - 1; i >= 0; --i) {
    for (int j = 0; j < n; ++j) {
      if (str[i] == str[j]) dist[i][j] = dist[i + 1][j + 1] + 1;
    }
  }

  dp[0][0] = 1;
  dpSum[0].assign(n + 1, 1);
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= i; ++j) {
      int head = i - j;
      if (str[head] == '0') continue;

      int prev_head = head - j;
      if (prev_head < 0) {
        dp[i][j] = dpSum[head][j];
        continue;
      }

      // string last = str.substr(head, j);
      // string prev = str.substr(prev_head, j);
      int d = dist[head][prev_head];

      // if (last > prev) {
      if (d < j && str[head + d] > str[prev_head + d]) {
        dp[i][j] = dpSum[head][j];
      } else {
        dp[i][j] = dpSum[head][j - 1];
      }
    }

    for (int j = 1; j <= n; ++j) {
      dpSum[i][j] = dpSum[i][j - 1] + dp[i][j];
      if (dpSum[i][j] > MOD) dpSum[i][j] -= MOD;
    }
  }
  cout << dpSum[n][n] << endl;
}