QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#561107#7876. Cyclic SubstringsHJRML 507ms1048076kbC++232.4kb2024-09-12 20:10:012024-09-12 20:10:05

Judging History

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

  • [2024-09-12 20:10:05]
  • 评测
  • 测评结果:ML
  • 用时:507ms
  • 内存:1048076kb
  • [2024-09-12 20:10:01]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define debug(x) cout<<#x<<": "<<x<<endl
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
using ll=long long;
using ull=unsigned long long;
// #define int long long
const int mo=998244353;
    struct Node{
        int cnt;
        int len;
        int fail;
        char s;
        vector<int> next;
        Node() : cnt{}, len{}, fail{},s{}{next.assign(10,0);}
    }; 
struct PAM {
    static constexpr int ALPHABET_SIZE = 10;
    int sz, tot, last;
    vector<Node> t;
    PAM() {
        init();
    }
    void init() {
        t.assign(2,Node());
        sz=-1;
        tot=last=1;
        newnode(0);
        newnode(-1);
        t[0].s = '$';
        t[0].fail = 1;
    }


    int newnode(int l) {  // 建立一个新节点,长度为 l
        sz++;
        t[sz].len = l;
        t[sz].fail = t[sz].cnt = 0;
        return sz;
    }

    int getfail(int x) {  // 找后缀回文
        while (t[tot - t[x].len - 1].s != t[tot].s) x = t[x].fail;
        return x;
    }

    void insert(char c) {  // 建树
        t.emplace_back();
        t[++tot].s = c;
        int now = getfail(last);
        if (!t[now].next[c - '0']) {
            int x = newnode(t[now].len + 2);
            t[x].fail = t[getfail(t[now].fail)].next[c - '0'];
            t[now].next[c - '0'] = x;
        }
        last = t[now].next[c - '0'];
        t[last].cnt++;
    }
    void work(){
        for(int i=tot;i>=2;i--){
            t[t[i].fail].cnt+=t[i].cnt;
            t[t[i].fail].cnt%=mo;
        }
    }
};
void solve(){
    int n;
    cin>>n;
    string s;
    cin>>s;
    PAM pam;
    for(auto x:s){
        pam.insert(x);
    }
    vector<Node> o=pam.t;
    pam.work();
    vector<Node> cur=pam.t;
    pam.t=o;
    for(auto x:s){
        pam.insert(x);
    }
    pam.work();
    ll ans=0;
    for(int i=2;i<=pam.tot;i++){
        ll cnt=pam.t[i].cnt,len=pam.t[i].len;
        if(len>n)
            continue;
        if(i<cur.size()){
            cnt-=cur[i].cnt;
        }
        ans+=cnt*cnt%mo*len%mo;
        ans%=mo;
    }
    cout<<ans<<endl;
}
signed main(){
    ios::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
    int t=1;
    while(t--){
        solve();
    }
}
/*
贡献法
正难则反
数小状压
关系连边
拆位
广义单调性
*/

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3600kb

input:

5
01010

output:

39

result:

ok 1 number(s): "39"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3816kb

input:

8
66776677

output:

192

result:

ok 1 number(s): "192"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3600kb

input:

1
1

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3576kb

input:

2
22

output:

12

result:

ok 1 number(s): "12"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3820kb

input:

2
21

output:

2

result:

ok 1 number(s): "2"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3808kb

input:

3
233

output:

10

result:

ok 1 number(s): "10"

Test #7:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

3
666

output:

54

result:

ok 1 number(s): "54"

Test #8:

score: 0
Accepted
time: 144ms
memory: 348180kb

input:

1000000
3333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333...

output:

496166704

result:

ok 1 number(s): "496166704"

Test #9:

score: 0
Accepted
time: 507ms
memory: 1046288kb

input:

3000000
2222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222...

output:

890701718

result:

ok 1 number(s): "890701718"

Test #10:

score: 0
Accepted
time: 471ms
memory: 1048076kb

input:

3000000
9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999...

output:

224009870

result:

ok 1 number(s): "224009870"

Test #11:

score: 0
Accepted
time: 448ms
memory: 1046768kb

input:

3000000
8989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989...

output:

51985943

result:

ok 1 number(s): "51985943"

Test #12:

score: -100
Memory Limit Exceeded

input:

3000000
1911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911...

output:

355676465

result: