UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#213769#2411. 三元组WZRYWZWY5048ms16840kbC++113.0kb2024-11-13 19:00:492024-11-13 23:00:49

answer

#pragma comment(linker, "/STACK:102400000,102400000")
#include <cstdio> // https://blog.csdn.net/u012015746/article/details/52104211 
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <string>
using namespace std;
typedef pair<int,int> Pii;
typedef long long LL;
typedef unsigned long long ULL;
typedef double DBL;
typedef long double LDBL;
#define MST(a,b) memset(a,b,sizeof(a))
#define CLR(a) MST(a,0)
#define SQR(a) ((a)*(a))
#define PCUT puts("\n----------")

const int maxn=1000000+10, MOD=998244353;
struct Manacher
{
    char str[2*maxn];
    int mana[2*maxn], len, res;
    int solve(char*);
};
struct RangeUpdate
{
    char *debug;
    int siz;
    int arr[maxn], delt[maxn];
    void init(int _n) {siz=_n; CLR(arr); CLR(delt);};
    void add(int,int,int,int);
    void update();
};
char str[maxn];
Manacher M;
RangeUpdate L, R;

int main()
{
    #ifdef LOCAL
//    freopen("in.txt", "r", stdin);
//  freopen("out.txt", "w", stdout);
    #endif
	int xxx; cin >> xxx;
    while(xxx--)
    {
    	cin >> str;
        M.solve(str);
        int len=strlen(str);
        L.init(len); R.init(len);
        for(int i=2, p, v, r; i<M.len; i++)
        {
            p = (i-1)/2, v=p+1;
            if(M.str[i]!='#')
            {
                r = (M.mana[i]+1)/2;
                L.add(p, p+r-1, v, -1);
                R.add(p-r+1, p, v+r-1, -1);
            }
            else
            {
                r = (M.mana[i]-1)/2;
                L.add(p, p+r-1, v-1, -1);
                R.add(p-r, p-1, v+r-1, -1);
            }
        }
        L.update(); R.update();
        LL ans=0;
        for(int i=0; i<len-1; i++)
        {
            ans = (ans + (LL)L.arr[i]*R.arr[i+1]%MOD)%MOD;
        }
        printf("%lld\n", (ans+MOD)%MOD);
    }
    return 0;
}

int Manacher::solve(char _str[])
{
    int tlen = strlen(_str);
    res = 0;
    str[0]='!';
    for(int i=0; i<tlen; i++)
    {
        str[2*i+1] = '#';
        str[2*i+2] = _str[i];
    }
    str[2*tlen+1]='#';
    str[2*tlen+2]=0;
    len = 2*tlen+2;
    mana[1]=1;
    int p=1, rm=1;
    for(int i=2; i<len; i++)
    {
        mana[i] = 1;
        if(rm>i)
        {
            mana[i] = min(rm-i+1, mana[2*p-i]);
        }
        while(str[i-mana[i]] == str[i+mana[i]] ) mana[i]++;
        if(i+mana[i]-1 > rm)
        {
            rm = i+mana[i]-1;
            p=i;
        }
        if(res < mana[i]) res = mana[i]-1;
    }
    return res;
}

void RangeUpdate::add(int l, int r, int x, int d)
{
    arr[l] = (arr[l]+x)%MOD; arr[r+1] = (arr[r+1] - (x+(LL)(r-l+1)*d%MOD)%MOD) %MOD;
    delt[l] = (delt[l]+d)%MOD; delt[r+1] = (delt[r+1]-d)%MOD;
}

void RangeUpdate::update()
{
    int sum=0, nd=0;
    for(int i=0; i<siz; i++)
    {
        sum = (sum+arr[i])%MOD;
        arr[i] = sum;
        nd = (nd + delt[i])%MOD;
        sum = (sum + nd)%MOD;
    }
}

Details

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 7ms
memory: 16824kb

input:

10
kyynjrttqngurtcvcjnnuqmstrntnpghrqqqp
lqfnqzykyzzynqnqyywzzwwfnyzlwykznyfhyknfnk
fuhjuhhuhuqjuuqu...

output:

27169
35530
31188
37732
65217
28457
133147
22985
43141
10759

result:

ok 10 lines

Test #2:

score: 10
Accepted
time: 17ms
memory: 16824kb

input:

10
eedleeeldeededlllleldleeeleleddleellele
kllrnnjqjniqqknjmlfcirjyrycfrkyqqjrky
uksfueafjuarusziepe...

output:

66808
20895
14900
37820
39914
38054
29364
37426
38775
29747

result:

ok 10 lines

Test #3:

score: 10
Accepted
time: 10ms
memory: 16828kb

input:

10
aaqzqvvvvzaqvazzvqqzqzavaaavvqaqqqvaqavvavvaavzvqzavaqvzvaazavqavazzvqvqazzvzvqqaqaaqqazqaqqzzzza...

output:

6230886
3556080
11774834
3833447
8206626
3621091
5300328
6484259
3025216
18509610

result:

ok 10 lines

Test #4:

score: 10
Accepted
time: 7ms
memory: 16836kb

input:

10
bsppzzcusncccbbpgguszngssnzncsnzpppbpuuczgcbucpupcubbzubsncncpbgbuzungnznsnpncpbugzcpguungzgcnbng...

output:

559443824
305794405
414279981
912202469
497470943
263140764
422669314
204178180
579056344
460822521

result:

ok 10 lines

Test #5:

score: 10
Accepted
time: 7ms
memory: 16840kb

input:

10
pzrpbfgjbnqhbpzohubzunqjnujfbfgazjqeaqhjgppqnogagegebuebhbeoeboouoojhbhaahjooggrozeephgqfrzrfrpjz...

output:

442803205
483459867
245377898
502317569
156660068
301473465
396310915
489306288
862513697
753896393

result:

ok 10 lines

Test #6:

score: 0
Time Limit Exceeded

input:

100000
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

341665830
471661
1999742
543480
459540
202296822
191363172
1241848
713235
369157
575809
170913820
68...

result:


Test #7:

score: 0
Time Limit Exceeded

input:

10000
iqtuiwnrdznudrwdznuwoyhzhhmiqytqhdqjuhihyuyrmwqurmdzdwiidomqrihqrjzyjwytjhznuwuhiojnhiduhytjir...

output:

452745570
395658802
415729637
581286624
608938037
896800719
444684505
913683462
444333468
228535301
...

result:


Test #8:

score: 0
Time Limit Exceeded

input:

1000
sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...

output:

845573779
254782300
56185577
239721206
427653199
812292186
496897443
160197728
268511769
327773907
7...

result:


Test #9:

score: 0
Time Limit Exceeded

input:

100
yuuxiorshssxoiyxrsxyyyuxsuyuhsruhxisoyiuuixhrsxuxyyxxosihhyisxxohoyiiurxhixrruryiihxhsxhxuhoroou...

output:

732636589
377635994
204944545
800901731
855220417
505651421
500433866
804284443
619658341
415348374
...

result:


Test #10:

score: 0
Time Limit Exceeded

input:

10
qvvvvqqgqgvvvgqvgqvqqwqgwqvqggvgqqqgqvwwggwwqqqqqwvwqggqvgqqvvvvvwqvqvvgvvqgvwqggwqqvvwwvvgwwwgqg...

output:

277639311
181813441
852565296
302618524
261112096

result: