QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#113033 | #6567. Repetitive String Invention | rniya | AC ✓ | 125ms | 8352kb | C++17 | 3.2kb | 2023-06-16 00:30:13 | 2023-06-16 00:30:15 |
Judging History
answer
#include <bits/stdc++.h>
#ifdef LOCAL
#include <debug.hpp>
#else
#define debug(...) void(0)
#endif
template <typename T> std::vector<int> Z_Algorithm(const T& s) {
int n = s.size();
std::vector<int> z(n);
z[0] = n;
for (int i = 1, j = 0; i < n;) {
while (i + j < n and s[j] == s[i + j]) j++;
z[i] = j;
if (j == 0) {
i++;
continue;
}
int k = 1;
while (i + k < n and k + z[k] < j) z[i + k] = z[k], k++;
i += k;
j -= k;
}
return z;
}
template <typename T> std::vector<int> LCP(const T& s, const T& t) {
T u(s);
u.insert(u.begin(), t.begin(), t.end());
std::vector<int> z = Z_Algorithm(u);
for (int& i : z) i = std::min(i, (int)t.size());
return std::vector<int>(z.begin() + t.size(), z.end());
}
using namespace std;
typedef long long ll;
#define all(x) begin(x), end(x)
constexpr int INF = (1 << 30) - 1;
constexpr long long IINF = (1LL << 60) - 1;
constexpr int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
template <class T> istream& operator>>(istream& is, vector<T>& v) {
for (auto& x : v) is >> x;
return is;
}
template <class T> ostream& operator<<(ostream& os, const vector<T>& v) {
auto sep = "";
for (const auto& x : v) os << exchange(sep, " ") << x;
return os;
}
template <class T, class U = T> bool chmin(T& x, U&& y) { return y < x and (x = forward<U>(y), true); }
template <class T, class U = T> bool chmax(T& x, U&& y) { return x < y and (x = forward<U>(y), true); }
template <class T> void mkuni(vector<T>& v) {
sort(begin(v), end(v));
v.erase(unique(begin(v), end(v)), end(v));
}
template <class T> int lwb(const vector<T>& v, const T& x) { return lower_bound(begin(v), end(v), x) - begin(v); }
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string S;
cin >> S;
int n = S.size();
ll ans = 0;
auto calc1 = [&]() -> ll { // |S_1| > |S_2|
vector<vector<int>> lcp(n), rlcp(n);
for (int i = 0; i < n; i++) {
string T = S.substr(i, n - i);
lcp[i] = LCP(S, T);
}
reverse(all(S));
for (int i = 0; i < n; i++) {
string T = S.substr(i, n - i);
rlcp[i] = LCP(S, T);
}
reverse(all(S));
ll res = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int len = j - i, margin = min(len, lcp[i][j]);
for (int k = j + len; k <= n; k++) {
int maxi = min(len - 1, rlcp[n - k][n - j]);
res += max(0, maxi - max(1, len - margin) + 1);
}
}
}
return res;
};
auto calc2 = [&]() -> ll { // |S_1| = |S_2|
ll res = 0;
for (int i = 0; i < n; i++) {
string T = S.substr(i, n - i);
auto lcp = LCP(S, T);
for (int j = i + 1; j < n; j++) res += min(j - i, lcp[j]);
}
return res;
};
for (int _ = 0; _ < 2; _++) {
ans += calc1();
reverse(all(S));
debug(ans);
}
ans += calc2();
cout << ans << '\n';
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3428kb
input:
aaaa
output:
9
result:
ok single line: '9'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3540kb
input:
axabxbcxcdxd
output:
22
result:
ok single line: '22'
Test #3:
score: 0
Accepted
time: 13ms
memory: 4360kb
input:
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
536006700
result:
ok single line: '536006700'
Test #4:
score: 0
Accepted
time: 17ms
memory: 4348kb
input:
abababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababab...
output:
136016600
result:
ok single line: '136016600'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3432kb
input:
a
output:
0
result:
ok single line: '0'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3544kb
input:
ab
output:
0
result:
ok single line: '0'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3488kb
input:
aa
output:
1
result:
ok single line: '1'
Test #8:
score: 0
Accepted
time: 18ms
memory: 4344kb
input:
bbbbbrrrrbrbrrbrbrbrbbrrbbbbrrbrrbrbrbrrrrrbbbrrbrrbbrrrbbbbbrrrrbbrbbrrrrrbbrrrbbbbbrbbrbbbrbrrbrrrrrrrrbbrbrbbrrrrrrbbbbbrbrrrrbrrbbrbrrrrrbrbrbbrbrrbrrrrbrbbrbrrbrrbbbbrrrrrbrbbrbbrrrrrbrbrbrbbbrrrrrrrbbbbbbrrbrbrrrrrbbbrbrrrrbbbbrrbrrbbbbbbbrbbbbrrrbrbbbrrrrrrbbbbbrbrrbbbbrbrbrrbbrrrbbbrbbbrbbrr...
output:
209015
result:
ok single line: '209015'
Test #9:
score: 0
Accepted
time: 12ms
memory: 4404kb
input:
fkrryithikkpurfezufbthxxrtejxpprhrhurrfziigzgajipayrefarpxuggehkiggeppfjghuyejuagkjpiezhmfizgphkkfffifihrimuhgtgzykfupbprjyrbpbimapjmbkrhubzhgfhhpkrxgjgmkheiiugiyerggyukyfuuxgrehgayafzuxymxxabygpapbjxipkxgbxhzpekypfghaumukguaipphiyhzimzfmpmzahbmaagytygyekzhktbbheetxrbipgytppgbhkpimrybkbeirhrzytfehba...
output:
5696
result:
ok single line: '5696'
Test #10:
score: 0
Accepted
time: 16ms
memory: 4404kb
input:
ayeaecauuueerrcsyyyuayauarecyrruueeucacrrcesercyeasuscucscruaaresaeruurreeursssuyraeysurecacueuacycacsyuyeyusssassaasyuarrcecueayacucuyyrsasrycyrrcececyuccecyreyeccuesaasceasussaraeruyarcauarcecacrucryryseysauaucyaeyurueurerrccrayyyycccsuaaesrecurucerrascyacucucryarycayeesyysusserarseyrauyrryeacauec...
output:
18249
result:
ok single line: '18249'
Test #11:
score: 0
Accepted
time: 17ms
memory: 4400kb
input:
lclccclcclllccccclcclclcccclllllcclcclclcclllllcllccclclclccclccllcclccccccllccclclcccclclcclclccclllllccclcccccclllllccllcclclllllllccclllcllllccccccccllccclllccclcllllllllcclccclccccllccllclclcclcllcllccclcllclllclclllclllcllcclclllccclcclclllclllllllcclllcccccllcllcllcclcclcllccclclllclclcccllcll...
output:
207835
result:
ok single line: '207835'
Test #12:
score: 0
Accepted
time: 16ms
memory: 4356kb
input:
lygxvkxeeiixzzpamosqadacrnyierrztikxheupgbkfkstyjrmyvhmjrhfhwfdeyhzuyhhbczbjgcnzouiufetegmnvxoeqxiykkwysdnnmdjtpwwzpdaqzmwmapbqbdjsdoxmpbvseyfrrqpgteehoxqsjszykfqgdmcgwikavcnhoubonianpecjtumdutpxwioqtkystzndrbtlfircdsnsxraoitswvhjirqxxjrnjjsldbmdcjngecdaotrgxvikyfyjlbbeketxrxeknuxmxehvabyyyxnrchukft...
output:
3442
result:
ok single line: '3442'
Test #13:
score: 0
Accepted
time: 18ms
memory: 4360kb
input:
yjjxyyxjxyjjyxyyjxyyjxjxjxjyxyxxjxjjyxxxxxjjxyxxyjjxxjyyjjjyyyxjyjxjxyjjyjxjyjyyxjyjyjyyxxyyxxxjjxxxyyyjjjyxjyxjxjyjxjyyyjjxxxjxxjxjjjyjxjyjyyxjyjyjyyxxyyxxxjjxxxyyyjjjyxjyxjxjyjxjyyyjjxxxjxxjxjyjjxyyxjxyjjyxyyjxyyjxjxjxjyxyxxjxjjyxxxxxjjxyxxyjjxxjyyjjjyyyxjyjxjxyjjxyyxjxyjjyxyyjxyyjxjxjxjyxyxxjxjjy...
output:
103111
result:
ok single line: '103111'
Test #14:
score: 0
Accepted
time: 19ms
memory: 4432kb
input:
lhllhlhlhllhlhllhhlhhhhllhhlhhhhllhhlhhhhllhllhhllhhlhhhhllhllhhhhhllhhlhhhhhlhllhlhhlhllhlhhhhllhllhhhllhhlhhhhhhlhllhlhllhhlhhhhhhlhllhlhhllhllllhllhhhlhllhlhhhllhhlhhhhhhllhhlhhhhlhllhlhllhllhhhhllhllllhllllhllllhlllhllhlhllhhlhhhhhhhllhlllhllhlhllhhlhhhhllhllllhlllhllhlhllhllhhhhhhhllhhlhhhhllhh...
output:
298186
result:
ok single line: '298186'
Test #15:
score: 0
Accepted
time: 12ms
memory: 4504kb
input:
blbllblbblbllblbblbllblblblbblllblbbllblbllblbblbllblbblbllblblblbbllblbllblblblbbllblbllblbblbllblblblbbllblbllblblblbbllblbllblbblbllblbblbllblblblbblllblbblllblbblllblbbllblbllblblblbblllblbblllblbbllblbllblblblbblllblbbllblbllblbblbllblbblbllblblblbblllblbblllblbbllblbllblblblbblllblbblllblbblll...
output:
510790
result:
ok single line: '510790'
Test #16:
score: 0
Accepted
time: 16ms
memory: 4316kb
input:
aqqaqaaqqaaqaqqaqaaqaqqaaqqaqaaqqaaqaqqaaqqaqaaqaqqaqaaqqaaqaqqaqaaqaqqaaqqaqaaqaqqaqaaqqaaqaqqaaqqaqaaqqaaqaqqaqaaqaqqaaqqaqaaqqaaqaqqaaqqaqaaqaqqaqaaqqaaqaqqaaqqaqaaqqaaqaqqaqaaqaqqaaqqaqaaqaqqaqaaqqaaqaqqaqaaqaqqaaqqaqaaqqaaqaqqaaqqaqaaqaqqaqaaqqaaqaqqaqaaqaqqaaqqaqaaqaqqaqaaqqaaqaqqaaqqaqaaqqaaq...
output:
584698
result:
ok single line: '584698'
Test #17:
score: 0
Accepted
time: 83ms
memory: 8280kb
input:
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
8554693400
result:
ok single line: '8554693400'
Test #18:
score: 0
Accepted
time: 115ms
memory: 8236kb
input:
abababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababab...
output:
2154733200
result:
ok single line: '2154733200'
Test #19:
score: 0
Accepted
time: 117ms
memory: 8256kb
input:
abbbabbaaababbaabaaababaababbaabbbbbaaababbbbababbaabababaabbbaaabbababbababbabbbaabbabaaabaaabbbabbabbabaaaabbabbbababaabaabbaaaabbbbbbbababaabaababaaaaaabbbbbbbaaabaabaababbabaabababbbbabbabbaabbbaaababbbbabababababaabbbbbbbbbabbbbababaaabbbaababbbbaabbbbaabbaababbaaaababbabbabbabbabbaaaaaabbbbaab...
output:
930632
result:
ok single line: '930632'
Test #20:
score: 0
Accepted
time: 125ms
memory: 8352kb
input:
acbaabcbabcccccbbaaacaaacbacaabccbbccabbbaaacacbaccbaaaaaacbbcbabacaabaaabcbccbbccbaaabacacccacccbabcbbcaaabbaacaaabaabcaaccbacacbcbcacbbbbaacbbcccbbccabcacaaabcbbbbacbcbcaabbbccaabbcbacbcaccabbbcccccbcbbbabcabcacbccccacabccbccbccaaccbbbbbccbabbbcaabbaacaccacbcbaabbbbabbccbcacacbbcacbbccbacbbbcacccc...
output:
304687
result:
ok single line: '304687'
Test #21:
score: 0
Accepted
time: 109ms
memory: 8252kb
input:
gvqghqqtyruttomyqtjlimqxhhoiboxzggiduzwyaagmtvvogqwcfsgvnvzncgmhtpjtmnqekqyhzyvvnfofasxkcvrhlydmpfulmeugpayixcixaijfmkvhhbgikpyjlmvzrzbkhmtymjfkqzwafvimebzixveouiuwlkljnilpzdvrcygbtdsimysonrpolsunmdeqgatgudbkuihzgkqgucfczlhytrshtdhlvekmhnjllqfpkjwwujiifikmfvcpijojmnkjivvmbuweauqofpxnazdyisttwabrofjz...
output:
13605
result:
ok single line: '13605'
Test #22:
score: 0
Accepted
time: 103ms
memory: 8312kb
input:
abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmn...
output:
14989915
result:
ok single line: '14989915'
Test #23:
score: 0
Accepted
time: 114ms
memory: 8232kb
input:
aqqaqaaqqaaqaqqaqaaqaqqaaqqaqaaqqaaqaqqaaqqaqaaqaqqaqaaqqaaqaqqaqaaqaqqaaqqaqaaqaqqaqaaqqaaqaqqaaqqaqaaqqaaqaqqaqaaqaqqaaqqaqaaqqaaqaqqaaqqaqaaqaqqaqaaqqaaqaqqaaqqaqaaqqaaqaqqaqaaqaqqaaqqaqaaqaqqaqaaqqaaqaqqaqaaqaqqaaqqaqaaqqaaqaqqaaqqaqaaqaqqaqaaqqaaqaqqaqaaqaqqaaqqaqaaqaqqaqaaqqaaqaqqaaqqaqaaqqaaq...
output:
2798983
result:
ok single line: '2798983'