Codeforces Good Bye 2015 D: New Year and Ancient Prophecy

解法

Rolling-Hashing で文字列の大小関係をO(log N)で求めようのコーナー
kenkoooo.hatenablog.com

コード

#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;

class RollingHash {
 private:
  vector<long long> mod;
  void init() {
    // mod.push_back(999999937LL);
    mod.push_back(1000000009LL);
  }
  const long long base = 1000000007LL;
  int n;
  vector<vector<long long>> hs, pw;
  RollingHash() {}

 public:
  int cnt = 0;

  RollingHash(const string& s) : n(s.size()) {
    init();
    hs.resize(mod.size()), pw.resize(mod.size());
    for (int i = 0; i < mod.size(); i++) {
      hs[i].assign(n + 1, 0);
      pw[i].assign(n + 1, 0);
      hs[i][0] = 0;
      pw[i][0] = 1;
      for (int j = 0; j < n; j++) {
        // pw[i][j + 1] = pw[i][j] * base % mod[i];
        // hs[i][j + 1] = (hs[i][j] * base + s[j]) % mod[i];
        pw[i][j + 1] = pw[i][j] * base;
        hs[i][j + 1] = (hs[i][j] * base + s[j]);
      }
    }
  }

  inline long long hash(int l, int r, int i) {
    // return ((hs[i][r] - hs[i][l] * pw[i][r - l]) % mod[i] + mod[i]) % mod[i];
    return hs[i][r] - hs[i][l] * pw[i][r - l];
  }

  inline bool match(int l1, int r1, int l2, int r2) {
    bool ret = 1;
    for (int i = 0; i < mod.size(); i++)
      ret &= hash(l1, r1, i) == hash(l2, r2, i);
    return ret;
  }

  int lcp(int i, int j) {
    int l = 0, r = min(n - i, n - j) + 1;
    while (l + 1 < r) {
      int m = (l + r) / 2;
      if (match(i, i + m, j, j + m))
        l = m;
      else
        r = m;
    }
    return l;
  }
};

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

  RollingHash rocknrolling(str);

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

  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 k = rocknrolling.lcp(head, prev_head);

      // if (last > prev) {
      if (k < j && str[head + k] > str[prev_head + k]) {
        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]) % MOD;
    }
  }
  cout << dpSum[n][n] << endl;
}