QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#413086#6567. Repetitive String InventionLspeed#AC ✓1232ms3724kbC++143.8kb2024-05-17 03:25:292024-05-17 03:25:30

Judging History

你现在查看的是最新测评结果

  • [2024-05-17 03:25:30]
  • 评测
  • 测评结果:AC
  • 用时:1232ms
  • 内存:3724kb
  • [2024-05-17 03:25:29]
  • 提交

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'