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