QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#275965#7876. Cyclic Substringskath#AC ✓80ms329620kbC++171.6kb2023-12-05 13:11:202023-12-05 13:11:20

Judging History

你现在查看的是最新测评结果

  • [2023-12-05 13:11:20]
  • 评测
  • 测评结果:AC
  • 用时:80ms
  • 内存:329620kb
  • [2023-12-05 13:11:20]
  • 提交

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