ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#213769 | #2411. 三元组 | WZRYWZWY | 50 | 48ms | 16840kb | C++11 | 3.0kb | 2024-11-13 19:00:49 | 2024-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