QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#274616 | #7876. Cyclic Substrings | WilliamHu | TL | 100ms | 198920kb | C++20 | 1.4kb | 2023-12-03 18:27:02 | 2023-12-03 18:27:02 |
Judging History
answer
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
int n, ch[3000010][11], fail[3000010], len[3000010], pos = 0, las;
char s[3000010];
long long mod = 998244353;
long long cnt[3000010], tmp[3000010];
void init()
{
pos = 1;
len[0] = 0;
fail[0] = 1;
len[1] = -1;
fail[1] = 1;
las = 0;
}
int find(int x, int now)
{
while(s[now - len[x] - 1] != s[now])x = fail[x];
return x;
}
void insert(int x)
{
int p = find(las, x);
if(! ch[p][s[x] - '0'])
{
len[++ pos] = len[p] + 2;
fail[pos] = ch[find(fail[p], x)][s[x] - '0'];
ch[p][s[x] - '0'] = pos;
}
++ cnt[las = ch[p][s[x] - '0']];
}
signed main() {
cin>>n;
s[0] = '*';
for(int i = 1;i <= n;i ++)
{
cin>>s[i];
s[n + i] = s[i];
}
init();
for(int i = 1;i <= n;i ++)
{
insert(i);
//cout<<i<<endl;
}
for(int i = 1;i <= pos;i ++)tmp[i] = cnt[i];
// for(int i = 1;i <= n;i ++)
// {
//
// }
memset(ch, 0, sizeof(ch));
memset(fail, 0, sizeof(fail));
memset(cnt, 0, sizeof(cnt));
memset(len, 0, sizeof(len));
pos = 0;
long long ans = 0;
init();
for(int i = 1;i <= 2 * n;i ++)
{
insert(i);
//cout<<i<<endl;
}
for(int i = pos;i > 0;i --)
{
cnt[fail[i]] = (cnt[fail[i]]+ cnt[i]) % mod;
tmp[fail[i]] = (tmp[fail[i]] + tmp[i]) % mod;
if(len[i] <= n)ans = (ans + (cnt[i] - tmp[i] + mod) % mod * (cnt[i] - tmp[i] + mod) % mod * len[i] % mod) % mod;
}
cout<<ans;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 4ms
memory: 184244kb
input:
5 01010
output:
39
result:
ok 1 number(s): "39"
Test #2:
score: 0
Accepted
time: 3ms
memory: 183784kb
input:
8 66776677
output:
192
result:
ok 1 number(s): "192"
Test #3:
score: 0
Accepted
time: 4ms
memory: 182444kb
input:
1 1
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 3ms
memory: 184184kb
input:
2 22
output:
12
result:
ok 1 number(s): "12"
Test #5:
score: 0
Accepted
time: 4ms
memory: 182428kb
input:
2 21
output:
2
result:
ok 1 number(s): "2"
Test #6:
score: 0
Accepted
time: 3ms
memory: 180616kb
input:
3 233
output:
10
result:
ok 1 number(s): "10"
Test #7:
score: 0
Accepted
time: 3ms
memory: 180540kb
input:
3 666
output:
54
result:
ok 1 number(s): "54"
Test #8:
score: 0
Accepted
time: 100ms
memory: 198920kb
input:
1000000 3333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333...
output:
496166704
result:
ok 1 number(s): "496166704"
Test #9:
score: -100
Time Limit Exceeded
input:
3000000 2222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222...