ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#213767 | #2411. 三元组 | WZRYWZWY | 30 | 45ms | 16836kb | C++11 | 3.1kb | 2024-11-13 18:54:27 | 2024-11-13 23:00:39 |
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=1000000007;
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;
}
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 10ms
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: 8ms
memory: 16828kb
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: 7ms
memory: 16828kb
input:
10 aaqzqvvvvzaqvazzvqqzqzavaaavvqaqqqvaqavvavvaavzvqzavaqvzvaazavqavazzvqvqazzvzvqqaqaaqqazqaqqzzzza...
output:
6230886 3556080 11774834 3833447 8206626 3621091 5300328 6484259 3025216 18509610
result:
ok 10 lines
Test #4:
score: 0
Wrong Answer
time: 7ms
memory: 16836kb
input:
10 bsppzzcusncccbbpgguszngssnzncsnzpppbpuuczgcbucpupcubbzubsncncpbgbuzungnznsnpncpbugzcpguungzgcnbng...
output:
559443824 304038751 414279981 912202469 497470943 261385110 422669314 202422526 579056344 460822521
result:
wrong answer 2nd lines differ - expected: '305794405', found: '304038751'
Test #5:
score: 0
Wrong Answer
time: 13ms
memory: 16836kb
input:
10 pzrpbfgjbnqhbpzohubzunqjnujfbfgazjqeaqhjgppqnogagegebuebhbeoeboouoojhbhaahjooggrozeephgqfrzrfrpjz...
output:
442803205 483459867 243622244 502317569 661160293 296206503 396310915 489306288 862513697 753896393
result:
wrong answer 3rd lines differ - expected: '245377898', found: '243622244'
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 717693339 893289411 444684505 913683462 444333468 226779647 ...
result:
Test #8:
score: 0
Time Limit Exceeded
input:
1000 sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...
output:
656345819 585155360 885784589 182517211 686767218 839659877 619070450 990546387 616441369 319166499 ...
result:
Test #9:
score: 0
Time Limit Exceeded
input:
100 yuuxiorshssxoiyxrsxyyyuxsuyuhsruhxisoyiuuixhrsxuxyyxxosihhyisxxohoyiiurxhixrruryiihxhsxhxuhoroou...
output:
779765491 376458721 422870048 178362162 649823318 585922481 294917151 695687546 914024349 995423932 ...
result:
Test #10:
score: 0
Time Limit Exceeded
input:
10 qvvvvqqgqgvvvgqvgqvqqwqgwqvqggvgqqqgqvwwggwwqqqqqwvwqggqvgqqvvvvvwqvqvvgvvqgvwqggwqqvvwwvvgwwwgqg...
output:
954510220 460188183 921444132 566463862 809208050 369579100 381010684 360533500