QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#648014	#7876. Cyclic Substrings	Tmonkey	TL	11ms	105436kb	C++14	4.7kb	2024-10-17 16:35:05	2024-10-17 16:37:16

Judging History

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

[2024-10-17 16:37:16]
评测

测评结果：TL
用时：11ms
内存：105436kb

查看

[2024-10-17 16:35:05]
提交

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 + 10;
const int M = 1e6 + 10;
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];
int nxt[M][26];
int lef[N];
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;
    // 奇数
    int flag = 1;
    for (int i = 0, l = 0, r = -1; i < n + n / 2; i++)
    {
        int k = 0, pos = 0;
        if (i <= r && i < n)
        {
            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 (i >= n)
        {
            if (flag)
            {
                flag = 0;
                l = n, r = n - 1;
            }
            k = d[i - n], pos = lef[i - n];
        }
        if (pos && i < n)
            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 < 25; 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;
        }
    }
    dfs1(0);
    for (int i = 0; i <= cnt1; i++)
    {
        trie[i].add = trie[i].h = trie[i].num = 0;
    }
    // 偶数
    flag = 1;
    for (int i = 0, l = 0, r = -1; i < n + n / 2; i++)
    {
        int k = 0, pos = 0;
        if (i <= r && i < n)
        {
            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 (i >= n)
        {
            if (flag)
            {
                flag = 0;
                l = n, r = n - 1;
            }
            k = d[i - n], pos = lef[i - n];
        }
        if (pos && i < n)
            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 < 25; 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;
        }
    }
    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;
}

源文件, 语言: C++14

详细

Test #1:

score: 100

Accepted

time: 4ms

memory: 105204kb

input:

5
01010

output:

result:

ok 1 number(s): "39"

Test #2:

score: 0

Accepted

time: 4ms

memory: 105404kb

input:

8
66776677

output:

result:

ok 1 number(s): "192"

Test #3:

score: 0

Accepted

time: 0ms

memory: 105152kb

input:

1
1

output:

result:

ok 1 number(s): "1"

Test #4:

score: 0

Accepted

time: 11ms

memory: 105240kb

input:

2
22

output:

result:

ok 1 number(s): "12"

Test #5:

score: 0

Accepted

time: 3ms

memory: 105432kb

input:

2
21

output:

result:

ok 1 number(s): "2"

Test #6:

score: 0

Accepted

time: 0ms

memory: 105436kb

input:

3
233

output:

result:

ok 1 number(s): "10"

Test #7:

score: 0

Accepted

time: 7ms

memory: 105196kb

input:

3
666

output:

result:

ok 1 number(s): "54"

Test #8:

score: -100

Time Limit Exceeded

input:

1000000
3333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333...