QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#648188#7876. Cyclic SubstringsTmonkeyRE 1022ms606860kbC++204.6kb2024-10-17 17:33:592024-10-17 17:34:00

Judging History

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

  • [2024-10-17 17:34:00]
  • 评测
  • 测评结果:RE
  • 用时:1022ms
  • 内存:606860kb
  • [2024-10-17 17:33:59]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
using namespace std;
#define YES "YES"
#define NO "NO"
#define all(a) a.begin(), a.end()
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
const double eps = 1e-9;
const int N = 3e6 + 100;
const int M = 1e6 + 5e5 + 100;
const int INF = 1e16 + 100;
const int mod = 998244353;
const int base = 23333;
mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
int n, cnt1, cnt2, ans;
string s;
int d[N + N / 2];
int nxt[M][24];
int lef[N + N / 2];
struct node
{
    int son[10], num = 0, add = 0, h = 0;
} trie[M];
void dfs1(int u)
{
    for (int i = 0; i < 10; i++)
    {
        int v = trie[u].son[i];
        if (v)
        {
            dfs1(v);
            trie[u].add = (trie[u].add + trie[v].add) % mod;
        }
        trie[u].son[i] = 0;
    }
    trie[u].num = (trie[u].num + trie[u].add) % mod;
    if (trie[u].h)
        ans = (ans + trie[u].num * trie[u].num % mod * (2 * trie[u].h - 1) % mod) % mod;
}
void dfs2(int u)
{
    for (int i = 0; i < 10; i++)
    {
        int v = trie[u].son[i];
        if (v)
        {
            dfs2(v);
            trie[u].add = (trie[u].add + trie[v].add) % mod;
        }
    }
    trie[u].num = (trie[u].num + trie[u].add) % mod;

    ans = (ans + trie[u].num * trie[u].num % mod * (2 * trie[u].h) % mod) % mod;
}
int get(int u, int k)
{
    int i = 0;
    while (k)
    {
        if (k & 1)
            u = nxt[u][i];
        k = k >> 1;
        i++;
    }
    return u;
}
void solve()
{
    cin >> n;
    cin >> s;
    s = s + s;
    // 奇数
    for (int i = 0, l = 0, r = -1; i < n + n / 2; i++)
    {
        int k = 0, pos = 0;
        if (i <= r)
        {
            k = min(d[l + r - i], r - i + 1);
            pos = lef[l + r - i];
            if (d[l + r - i] > r - i + 1)
                pos = get(pos, trie[pos].h - (r - i + 1));
        }
        if (pos)
            trie[pos].add++;
        while (0 <= i - k && i + k < 2 * n && k < (n + 1) / 2 && s[i - k] == s[i + k])
        {
            int v = s[i + k] - '0';
            if (!trie[pos].son[v])
                trie[pos].son[v] = ++cnt1;
            int x = trie[pos].son[v];
            trie[x].num++;
            trie[x].h = trie[pos].h + 1;

            // update

            nxt[x][0] = pos;
            for (int j = 1; j < 24; j++)
            {
                if ((1 << j) > trie[x].h)
                    break;
                nxt[x][j] = nxt[nxt[x][j - 1]][j - 1];
            }

            pos = trie[pos].son[v];
            k++;
        }
        d[i] = k--;
        lef[i] = pos;
        if (i + k > r)
        {
            l = i - k;
            r = i + k;
        }
    }
    if (s[0] == s[1] == '9')
    {
        cout << 9 << '\n';
        return;
    }
    for (int i = 0; i < n / 2; i++)
    {
        trie[lef[i]].add = (trie[lef[i]].add + mod - 1) % mod;
    }
    dfs1(0);

    for (int i = 0; i <= cnt1; i++)
    {
        trie[i].add = trie[i].h = trie[i].num = 0;
    }
    // 偶数
    for (int i = 0, l = 0, r = -1; i < n + n / 2; i++)
    {
        int k = 0, pos = 0;
        if (i <= r)
        {
            k = min(d[l + r - i + 1], r - i + 1);
            pos = lef[l + r - i + 1];
            if (d[l + r - i + 1] > r - i + 1)
                pos = get(pos, trie[pos].h - (r - i + 1));
        }
        if (pos)
            trie[pos].add++;
        while (0 <= i - k - 1 && i + k < 2 * n && k < n / 2 && s[i - k - 1] == s[i + k])
        {
            int v = s[i + k] - '0';
            if (!trie[pos].son[v])
                trie[pos].son[v] = ++cnt2;
            int x = trie[pos].son[v];
            trie[x].num++;
            trie[x].h = trie[pos].h + 1;

            // update

            nxt[x][0] = pos;
            for (int j = 1; j < 24; j++)
            {
                if ((1 << j) > trie[x].h)
                    break;
                nxt[x][j] = nxt[nxt[x][j - 1]][j - 1];
            }

            pos = trie[pos].son[v];
            k++;
        }
        d[i] = k--;
        lef[i] = pos;
        if (i + k > r)
        {
            l = i - k - 1;
            r = i + k;
        }
    }
    for (int i = 0; i < n / 2; i++)
    {
        trie[lef[i]].add = (trie[lef[i]].add + mod - 1) % mod;
    }
    dfs2(0);
    cout << ans << '\n';
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}

详细

Test #1:

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

input:

5
01010

output:

39

result:

ok 1 number(s): "39"

Test #2:

score: 0
Accepted
time: 11ms
memory: 161612kb

input:

8
66776677

output:

192

result:

ok 1 number(s): "192"

Test #3:

score: 0
Accepted
time: 3ms
memory: 161512kb

input:

1
1

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 8ms
memory: 161260kb

input:

2
22

output:

12

result:

ok 1 number(s): "12"

Test #5:

score: 0
Accepted
time: 7ms
memory: 160524kb

input:

2
21

output:

2

result:

ok 1 number(s): "2"

Test #6:

score: 0
Accepted
time: 8ms
memory: 162016kb

input:

3
233

output:

10

result:

ok 1 number(s): "10"

Test #7:

score: 0
Accepted
time: 11ms
memory: 160044kb

input:

3
666

output:

54

result:

ok 1 number(s): "54"

Test #8:

score: 0
Accepted
time: 294ms
memory: 311668kb

input:

1000000
3333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333...

output:

496166704

result:

ok 1 number(s): "496166704"

Test #9:

score: 0
Accepted
time: 1022ms
memory: 606860kb

input:

3000000
2222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222...

output:

890701718

result:

ok 1 number(s): "890701718"

Test #10:

score: -100
Runtime Error

input:

3000000
9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999...

output:


result: