Codeforces Good Bye 2015 D: New Year and Ancient Prophecy
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; }