QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#642624#7876. Cyclic Substringsucup-team1001WA 1ms3588kbC++202.4kb2024-10-15 15:21:202024-10-15 15:21:21

Judging History

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

  • [2024-10-15 15:21:21]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3588kb
  • [2024-10-15 15:21:20]
  • 提交

answer

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;
i64 mod = 998244353;

// 回文自动机
// T 字符集大小 , base 字符集基数
template<size_t T = 26, size_t base = 'a'>
class PAM {
private:
    class Node {
    public:
        int next[T];
        int fail;
        int len;
        i64 cnt;

        int x;


        Node() {
            memset(next, 0, sizeof(next));
            fail = 0;
            len = 0;
            cnt = 0;
        }
    };

    string s;
    vector<Node> tree;
    int last;
    int lim;

    // 获取节点 , 节点指针指向 x , 字符串长度指针指向i
    int getFail(int x, int i) {
        while (i - tree[x].len - 1 != i && s[i] != s[i - tree[x].len - 1]) {
            x = tree[x].fail;
        }
        return x;
    }

    int newNode(int len, int p) {
//        cerr << len << " " << p << endl;
        tree.push_back(Node());
        tree.back().len = len;
        tree.back().x = p;
        return tree.size() - 1;
    }

    void init() {
        tree.clear();
        newNode(0, -1);
        newNode(-1, -1);
        tree[0].fail = 1;
        last = 1;
    }

    void insert(int x, int i) {
        int p = getFail(last, i);
//        cerr << x << " " << i << endl;
        if (!tree[p].next[x]) {
            int np = newNode(tree[p].len + 2, x);
            tree[np].fail = tree[getFail(tree[p].fail, i)].next[x];
            tree[p].next[x] = np;
        }
        last = tree[p].next[x];
        if (i > lim) {
//            cerr << i << endl;
            tree[last].cnt++;
        }
    }

public:

    PAM(string _s, int lim) : s(_s), lim(lim) {
        init();
        s = "#" + s;
        for (int i = 1; i < s.size(); i++) {
            insert(s[i] - base, i);
        }
    }

    i64 solve() {
        i64 ans = 0;
        for (int i = tree.size() - 1; i >= 2; i--) {
            // 出现的次数
            tree[tree[i].fail].cnt += tree[i].cnt;
            tree[tree[i].fail].cnt %= mod;
            if (tree[i].len <= lim) {
                ans += 1ll * tree[i].cnt * tree[i].len % mod;
                ans %= mod;
            }
        }
        return ans;
    }
};


int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    s = s + s;
    PAM<10, '0'> pam(s, n);
    cout << pam.solve() << endl;
}

详细

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3588kb

input:

5
01010

output:

25

result:

wrong answer 1st numbers differ - expected: '39', found: '25'