QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#275965 | #7876. Cyclic Substrings | kath# | AC ✓ | 80ms | 329620kb | C++17 | 1.6kb | 2023-12-05 13:11:20 | 2023-12-05 13:11:20 |
Judging History
answer
#include <iostream>
#include <cstring>
using namespace std;
const int N=6000006,mod=998244353;
char s[N];
int pam[N][10],last,p,ni;
int fail[N],cnt[N],len[N],sz[N];
int lenlen;
int newnode(int l)
{
memset(pam[p], 0, sizeof(pam[p]));
cnt[p] = 0;
// num[p] = 0;
len[p] = l;
return p ++;
}
void init()
{
p = last = 0;
newnode(0), newnode(-1);
s[0] = '?';
fail[0] = 1;
}
int get_fail(int x)
{
while(s[ni - len[x] - 1] != s[ni])
x = fail[x];
return x;
}
void add(int c)
{
int old = get_fail(last);
if(!pam[old][c])
{
int now = newnode(len[old] + 2);
fail[now] = pam[get_fail(fail[old])][c];
pam[old][c] = now;
// num[now] = num[fail[now]] + 1;
}
last = pam[old][c];
cnt[last] ++;
}
void calc()
{
for(int i = p-1; i>=0; i--)
{
cnt[fail[i]] += cnt[i];
}
}
int main()
{
init();
scanf("%d", &lenlen);
scanf("%s", s+1);
for(int i=1+lenlen; i<=lenlen*2; i++)
s[i] = s[i-lenlen];
for(ni=1; ni<=lenlen; ni++)
add(s[ni]-'0');
for(int i=p-1; i>=0; i--)
sz[i] = cnt[i];
for(int i=p-1; i>=0; i--)
sz[fail[i]] += sz[i];
for(ni=lenlen+1; ni<=lenlen*2; ni++)
add(s[ni] - '0');
calc();
long long ans = 0;
for(int i=2; i<p; i++)
if(len[i] <= lenlen)
// cout << len[i] << " " << cnt[i] << " " << sz[i] << "\n",
ans = (ans + (1ll*(cnt[i] - sz[i])*(cnt[i] - sz[i])%mod) * len[i])%mod;
cout << ans << '\n';
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 13924kb
input:
5 01010
output:
39
result:
ok 1 number(s): "39"
Test #2:
score: 0
Accepted
time: 0ms
memory: 14072kb
input:
8 66776677
output:
192
result:
ok 1 number(s): "192"
Test #3:
score: 0
Accepted
time: 0ms
memory: 14076kb
input:
1 1
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 2ms
memory: 13944kb
input:
2 22
output:
12
result:
ok 1 number(s): "12"
Test #5:
score: 0
Accepted
time: 0ms
memory: 14012kb
input:
2 21
output:
2
result:
ok 1 number(s): "2"
Test #6:
score: 0
Accepted
time: 2ms
memory: 14068kb
input:
3 233
output:
10
result:
ok 1 number(s): "10"
Test #7:
score: 0
Accepted
time: 2ms
memory: 13964kb
input:
3 666
output:
54
result:
ok 1 number(s): "54"
Test #8:
score: 0
Accepted
time: 24ms
memory: 123824kb
input:
1000000 3333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333...
output:
496166704
result:
ok 1 number(s): "496166704"
Test #9:
score: 0
Accepted
time: 79ms
memory: 327464kb
input:
3000000 2222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222...
output:
890701718
result:
ok 1 number(s): "890701718"
Test #10:
score: 0
Accepted
time: 78ms
memory: 167836kb
input:
3000000 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999...
output:
224009870
result:
ok 1 number(s): "224009870"
Test #11:
score: 0
Accepted
time: 74ms
memory: 327376kb
input:
3000000 8989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989...
output:
51985943
result:
ok 1 number(s): "51985943"
Test #12:
score: 0
Accepted
time: 64ms
memory: 329620kb
input:
3000000 1911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911...
output:
355676465
result:
ok 1 number(s): "355676465"
Test #13:
score: 0
Accepted
time: 68ms
memory: 294800kb
input:
3000000 7777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777...
output:
788510374
result:
ok 1 number(s): "788510374"
Test #14:
score: 0
Accepted
time: 80ms
memory: 309144kb
input:
3000000 5555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555...
output:
691884476
result:
ok 1 number(s): "691884476"
Test #15:
score: 0
Accepted
time: 64ms
memory: 182056kb
input:
3000000 0990990909909909099090990990909909909099090990990909909099099090990990909909099099090990990909909099099090990909909909099099090990909909909099090990990909909909099090990990909909909099090990990909909099099090990990909909099099090990990909909099099090990909909909099099090990909909909099090990...
output:
701050848
result:
ok 1 number(s): "701050848"
Test #16:
score: 0
Accepted
time: 46ms
memory: 71464kb
input:
3000000 2772772727727727277272772772727727727277272772772727727277277272772772727727277277272772772727727277277272772727727727277277272772727727727277272772772727727727277272772772727727727277272772772727727277277272772772727727277277272772772727727277277272772727727727277277272772727727727277272772...
output:
486861605
result:
ok 1 number(s): "486861605"
Test #17:
score: 0
Accepted
time: 63ms
memory: 284504kb
input:
3000000 4554554545545545455454554554545545545455454554554545545455455454554554545545455455454554554545545455455454554545545545455455454554545545545455454554554545545545455454554554545545545455454554554545545455455454554554545545455455454554554545545455455454554545545545455455454554545545545455454554...
output:
450625621
result:
ok 1 number(s): "450625621"
Test #18:
score: 0
Accepted
time: 62ms
memory: 278360kb
input:
3000000 1181811811818118181181181811818118118181181181811818118118181181181811818118118181181811811818118118181181811811818118181181181811811818118181181181811811818118181181181811818118118181181181811818118118181181181811818118118181181811811818118118181181811811818118181181181811811818118181181181...
output:
649551870
result:
ok 1 number(s): "649551870"
Extra Test:
score: 0
Extra Test Passed