Submission #856648

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
string w;
int L;
vector<vector<int>> G;
map<int, pair<int,int>> memo;
pair<int,int> f(int p) {
	if (p == L) return {0, 1};
	if (memo.count(p)) return memo[p];
	int r1 = 1 << 30;
	int r2 = 0;
	for (int x : G[p]) {
		auto q = f(x);
		++ q.first;
		if (q.first < r1) {
			r1 = q.first;
			r2 = q.second;
		} else if (q.first == r1) {
			r2 += q.second;
			r2 %= mod;
		}
	}
	return memo[p] = {r1, r2};
}
int main() {
	cin >> w;
	L = w.length();
	if (L > 4000) throw 1;
	G.resize(L);
	vector<vector<int>> hh(L, vector<int>(L+1));
	for (int i = 0; i < L; ++ i) {
		hh[i][0] = 0;
		for (int j = 1; i+j <= L; ++ j) {
			hh[i][j] = hh[i][j-1] * 37 + w[i+j-1];
		}
	}
	for (int i = 0; i < L; ++ i) {
		vector<bool> hoge(L+1, true);
		for (int len = 1; i + len*2 <= L; ++ len) {
			int s = hh[i][len];
			for (int k = 2; i + len*k <= L; ++ k) {
				if (hh[i+(k-1)*len][len] != s) break;
				hoge[i+len*k] = false;
			}
		}
		for (int j = i+1; j <= L; ++ j) {
			if (hoge[j]) G[i].push_back(j);
		}
	}
	auto r = f(0);
	cout << r.first << endl;
	cout << r.second << endl;
}

Submission Info

Judge Result