QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#413086 | #6567. Repetitive String Invention | Lspeed# | AC ✓ | 1232ms | 3724kb | C++14 | 3.8kb | 2024-05-17 03:25:29 | 2024-05-17 03:25:30 |
Judging History
answer
#include <iostream> // Input/output stream objects
#include <fstream> // File stream objects
#include <sstream> // String stream objects
#include <iomanip> // Input/output manipulators
#include <string> // String class and functions
#include <vector> // Dynamic array
#include <list> // Doubly linked list
#include <set> // Set container
#include <map> // Map container
#include <queue> // Queue container
#include <stack> // Stack container
#include <algorithm> // Algorithms on sequences (e.g., sort, find)
#include <cmath> // Mathematical functions
#include <climits> // LLONG_MAX, LLONG_MIN
#include <ctime> // Date and time functions
#include <cstdlib> // General purpose functions (e.g., memory management)
#include <cstring> // C-style string functions
#include <cctype> // Character classification functions
#include <cassert> // Assert function for debugging
#include <exception> // Standard exceptions
#include <functional> // Function objects
#include <iterator> // Iterator classes
#include <limits> // Numeric limits
#include <locale> // Localization and internationalization
#include <numeric> // Numeric operations (e.g., accumulate)
#include <random> // Random number generators
#include <stdexcept> // Standard exception classes
#include <typeinfo> // Runtime type information
#include <utility> // Utility components (e.g., std::pair)
#include <bitset>
using namespace std;
#define FOR(i, a, b) for(int i = a; i < (b); i++)
#define FORE(i, a, b) for(int i = a; i <= (b); i++)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define x first
#define y second
#define mp make_pair
#define PI 3.141592653
#define compress(coord) sort(all(coord)), coord.resize(unique(all(coord)) - coord.begin())
const double eps = 1e-9; // x < eps (x <= 0) x < -eps (x < 0)
const ll inf = LLONG_MAX;
const int N = 810;
const ll base = 137, mod = 1e9 + 7;
vector<ll> basepow(N), baseinv(N), sumh(N);
string S;
int n;
ll mul(ll a, ll b) { return (a * b) % mod; }
ll add(ll a, ll b) { return (a + b) % mod; }
ll sub(ll a, ll b) { return (a - b + mod) % mod; }
ll calpow(ll a, ll b) {
ll ret = 1;
for (; b; b >>= 1) {
if (b & 1) ret = mul(ret, a);
a = mul(a, a);
}
return ret;
}
ll calhash(int l, int r) {
if (l < 1 || r > n) return -1;
return mul(sub(sumh[r], sumh[l-1]), baseinv[l]);
}
pair<ll, ll> solve(string s) {
FORE (i, 1, n+10) sumh[i] = 0;
FORE (i, 1, n) sumh[i] = sumh[i-1] + (basepow[i] * (s[i-1] - 'a'));
ll ans = 0, sym = 0;
FORE (i, 1, n) {
FORE (j, i, n) {
ll curhash = calhash(i, j);
ll cnt = 0;
if (curhash == calhash(j+1, 2*j-i+1)) sym++;
FORE (k, j+1, n) {
ll csym = calhash(k+1, k+j-i+1);
ll prevh = calhash(i-k+j, i-1);
ll nexth = calhash(j+1, k);
if (prevh == nexth) cnt++;
if (curhash == csym) {
// cout << i << " " << j << " " << k << endl;
sym++, ans += cnt;
}
}
}
}
return mp(ans, sym);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
basepow[0] = 1, baseinv[0] = 1;
FORE (i, 1, 800) basepow[i] = mul(basepow[i-1], base);
baseinv[1] = calpow(base, mod-2);
FORE (i, 2, 800) baseinv[i] = mul(baseinv[i-1], baseinv[1]);
cin >> S;
n = (int)S.length();
pair<ll, ll> ans1 = solve(S);
reverse(all(S));
pair<ll, ll> ans2 = solve(S);
// cout << ans1.x << " " << ans1.y << endl;
// cout << ans2.x << " " << ans2.y << endl;
cout << ans1.x + ans2.x + ans1.y <<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3656kb
input:
aaaa
output:
9
result:
ok single line: '9'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
axabxbcxcdxd
output:
22
result:
ok single line: '22'
Test #3:
score: 0
Accepted
time: 153ms
memory: 3660kb
input:
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
536006700
result:
ok single line: '536006700'
Test #4:
score: 0
Accepted
time: 153ms
memory: 3648kb
input:
abababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababab...
output:
136016600
result:
ok single line: '136016600'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
a
output:
0
result:
ok single line: '0'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
ab
output:
0
result:
ok single line: '0'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
aa
output:
1
result:
ok single line: '1'
Test #8:
score: 0
Accepted
time: 139ms
memory: 3628kb
input:
bbbbbrrrrbrbrrbrbrbrbbrrbbbbrrbrrbrbrbrrrrrbbbrrbrrbbrrrbbbbbrrrrbbrbbrrrrrbbrrrbbbbbrbbrbbbrbrrbrrrrrrrrbbrbrbbrrrrrrbbbbbrbrrrrbrrbbrbrrrrrbrbrbbrbrrbrrrrbrbbrbrrbrrbbbbrrrrrbrbbrbbrrrrrbrbrbrbbbrrrrrrrbbbbbbrrbrbrrrrrbbbrbrrrrbbbbrrbrrbbbbbbbrbbbbrrrbrbbbrrrrrrbbbbbrbrrbbbbrbrbrrbbrrrbbbrbbbrbbrr...
output:
209015
result:
ok single line: '209015'
Test #9:
score: 0
Accepted
time: 142ms
memory: 3576kb
input:
fkrryithikkpurfezufbthxxrtejxpprhrhurrfziigzgajipayrefarpxuggehkiggeppfjghuyejuagkjpiezhmfizgphkkfffifihrimuhgtgzykfupbprjyrbpbimapjmbkrhubzhgfhhpkrxgjgmkheiiugiyerggyukyfuuxgrehgayafzuxymxxabygpapbjxipkxgbxhzpekypfghaumukguaipphiyhzimzfmpmzahbmaagytygyekzhktbbheetxrbipgytppgbhkpimrybkbeirhrzytfehba...
output:
5696
result:
ok single line: '5696'
Test #10:
score: 0
Accepted
time: 152ms
memory: 3640kb
input:
ayeaecauuueerrcsyyyuayauarecyrruueeucacrrcesercyeasuscucscruaaresaeruurreeursssuyraeysurecacueuacycacsyuyeyusssassaasyuarrcecueayacucuyyrsasrycyrrcececyuccecyreyeccuesaasceasussaraeruyarcauarcecacrucryryseysauaucyaeyurueurerrccrayyyycccsuaaesrecurucerrascyacucucryarycayeesyysusserarseyrauyrryeacauec...
output:
18249
result:
ok single line: '18249'
Test #11:
score: 0
Accepted
time: 131ms
memory: 3648kb
input:
lclccclcclllccccclcclclcccclllllcclcclclcclllllcllccclclclccclccllcclccccccllccclclcccclclcclclccclllllccclcccccclllllccllcclclllllllccclllcllllccccccccllccclllccclcllllllllcclccclccccllccllclclcclcllcllccclcllclllclclllclllcllcclclllccclcclclllclllllllcclllcccccllcllcllcclcclcllccclclllclclcccllcll...
output:
207835
result:
ok single line: '207835'
Test #12:
score: 0
Accepted
time: 150ms
memory: 3724kb
input:
lygxvkxeeiixzzpamosqadacrnyierrztikxheupgbkfkstyjrmyvhmjrhfhwfdeyhzuyhhbczbjgcnzouiufetegmnvxoeqxiykkwysdnnmdjtpwwzpdaqzmwmapbqbdjsdoxmpbvseyfrrqpgteehoxqsjszykfqgdmcgwikavcnhoubonianpecjtumdutpxwioqtkystzndrbtlfircdsnsxraoitswvhjirqxxjrnjjsldbmdcjngecdaotrgxvikyfyjlbbeketxrxeknuxmxehvabyyyxnrchukft...
output:
3442
result:
ok single line: '3442'
Test #13:
score: 0
Accepted
time: 152ms
memory: 3652kb
input:
yjjxyyxjxyjjyxyyjxyyjxjxjxjyxyxxjxjjyxxxxxjjxyxxyjjxxjyyjjjyyyxjyjxjxyjjyjxjyjyyxjyjyjyyxxyyxxxjjxxxyyyjjjyxjyxjxjyjxjyyyjjxxxjxxjxjjjyjxjyjyyxjyjyjyyxxyyxxxjjxxxyyyjjjyxjyxjxjyjxjyyyjjxxxjxxjxjyjjxyyxjxyjjyxyyjxyyjxjxjxjyxyxxjxjjyxxxxxjjxyxxyjjxxjyyjjjyyyxjyjxjxyjjxyyxjxyjjyxyyjxyyjxjxjxjyxyxxjxjjy...
output:
103111
result:
ok single line: '103111'
Test #14:
score: 0
Accepted
time: 153ms
memory: 3576kb
input:
lhllhlhlhllhlhllhhlhhhhllhhlhhhhllhhlhhhhllhllhhllhhlhhhhllhllhhhhhllhhlhhhhhlhllhlhhlhllhlhhhhllhllhhhllhhlhhhhhhlhllhlhllhhlhhhhhhlhllhlhhllhllllhllhhhlhllhlhhhllhhlhhhhhhllhhlhhhhlhllhlhllhllhhhhllhllllhllllhllllhlllhllhlhllhhlhhhhhhhllhlllhllhlhllhhlhhhhllhllllhlllhllhlhllhllhhhhhhhllhhlhhhhllhh...
output:
298186
result:
ok single line: '298186'
Test #15:
score: 0
Accepted
time: 152ms
memory: 3720kb
input:
blbllblbblbllblbblbllblblblbblllblbbllblbllblbblbllblbblbllblblblbbllblbllblblblbbllblbllblbblbllblblblbbllblbllblblblbbllblbllblbblbllblbblbllblblblbblllblbblllblbblllblbbllblbllblblblbblllblbblllblbbllblbllblblblbblllblbbllblbllblbblbllblbblbllblblblbblllblbblllblbbllblbllblblblbblllblbblllblbblll...
output:
510790
result:
ok single line: '510790'
Test #16:
score: 0
Accepted
time: 152ms
memory: 3572kb
input:
aqqaqaaqqaaqaqqaqaaqaqqaaqqaqaaqqaaqaqqaaqqaqaaqaqqaqaaqqaaqaqqaqaaqaqqaaqqaqaaqaqqaqaaqqaaqaqqaaqqaqaaqqaaqaqqaqaaqaqqaaqqaqaaqqaaqaqqaaqqaqaaqaqqaqaaqqaaqaqqaaqqaqaaqqaaqaqqaqaaqaqqaaqqaqaaqaqqaqaaqqaaqaqqaqaaqaqqaaqqaqaaqqaaqaqqaaqqaqaaqaqqaqaaqqaaqaqqaqaaqaqqaaqqaqaaqaqqaqaaqqaaqaqqaaqqaqaaqqaaq...
output:
584698
result:
ok single line: '584698'
Test #17:
score: 0
Accepted
time: 1216ms
memory: 3672kb
input:
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
8554693400
result:
ok single line: '8554693400'
Test #18:
score: 0
Accepted
time: 1204ms
memory: 3644kb
input:
abababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababab...
output:
2154733200
result:
ok single line: '2154733200'
Test #19:
score: 0
Accepted
time: 1206ms
memory: 3724kb
input:
abbbabbaaababbaabaaababaababbaabbbbbaaababbbbababbaabababaabbbaaabbababbababbabbbaabbabaaabaaabbbabbabbabaaaabbabbbababaabaabbaaaabbbbbbbababaabaababaaaaaabbbbbbbaaabaabaababbabaabababbbbabbabbaabbbaaababbbbabababababaabbbbbbbbbabbbbababaaabbbaababbbbaabbbbaabbaababbaaaababbabbabbabbabbaaaaaabbbbaab...
output:
930632
result:
ok single line: '930632'
Test #20:
score: 0
Accepted
time: 1195ms
memory: 3632kb
input:
acbaabcbabcccccbbaaacaaacbacaabccbbccabbbaaacacbaccbaaaaaacbbcbabacaabaaabcbccbbccbaaabacacccacccbabcbbcaaabbaacaaabaabcaaccbacacbcbcacbbbbaacbbcccbbccabcacaaabcbbbbacbcbcaabbbccaabbcbacbcaccabbbcccccbcbbbabcabcacbccccacabccbccbccaaccbbbbbccbabbbcaabbaacaccacbcbaabbbbabbccbcacacbbcacbbccbacbbbcacccc...
output:
304687
result:
ok single line: '304687'
Test #21:
score: 0
Accepted
time: 1207ms
memory: 3576kb
input:
gvqghqqtyruttomyqtjlimqxhhoiboxzggiduzwyaagmtvvogqwcfsgvnvzncgmhtpjtmnqekqyhzyvvnfofasxkcvrhlydmpfulmeugpayixcixaijfmkvhhbgikpyjlmvzrzbkhmtymjfkqzwafvimebzixveouiuwlkljnilpzdvrcygbtdsimysonrpolsunmdeqgatgudbkuihzgkqgucfczlhytrshtdhlvekmhnjllqfpkjwwujiifikmfvcpijojmnkjivvmbuweauqofpxnazdyisttwabrofjz...
output:
13605
result:
ok single line: '13605'
Test #22:
score: 0
Accepted
time: 1232ms
memory: 3632kb
input:
abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmn...
output:
14989915
result:
ok single line: '14989915'
Test #23:
score: 0
Accepted
time: 1207ms
memory: 3572kb
input:
aqqaqaaqqaaqaqqaqaaqaqqaaqqaqaaqqaaqaqqaaqqaqaaqaqqaqaaqqaaqaqqaqaaqaqqaaqqaqaaqaqqaqaaqqaaqaqqaaqqaqaaqqaaqaqqaqaaqaqqaaqqaqaaqqaaqaqqaaqqaqaaqaqqaqaaqqaaqaqqaaqqaqaaqqaaqaqqaqaaqaqqaaqqaqaaqaqqaqaaqqaaqaqqaqaaqaqqaaqqaqaaqqaaqaqqaaqqaqaaqaqqaqaaqqaaqaqqaqaaqaqqaaqqaqaaqaqqaqaaqqaaqaqqaaqqaqaaqqaaq...
output:
2798983
result:
ok single line: '2798983'