QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #648003 | #7876. Cyclic Substrings | Tmonkey | TL | 10ms | 111524kb | C++14 | 4.8kb | 2024-10-17 16:33:25 | 2024-10-17 16:33:42 |
Judging History
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 i = 1; i < 25; i++)
{
if ((1 << i) > trie[x].h)
break;
nxt[x][i] = nxt[nxt[x][i - 1]][i - 1];
}
pos = trie[pos].son[v];
k++;
}
d[i] = k--;
lef[i] = pos;
if (i + k > r)
{
l = i - k;
r = i + k;
}
}
if (n > 1e5)
cout << 1 / 0;
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 i = 1; i < 25; i++)
{
if ((1 << i) > trie[x].h)
break;
nxt[x][i] = nxt[nxt[x][i - 1]][i - 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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 10ms
memory: 110516kb
input:
5 01010
output:
39
result:
ok 1 number(s): "39"
Test #2:
score: 0
Accepted
time: 4ms
memory: 109248kb
input:
8 66776677
output:
192
result:
ok 1 number(s): "192"
Test #3:
score: 0
Accepted
time: 4ms
memory: 110656kb
input:
1 1
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 7ms
memory: 109984kb
input:
2 22
output:
12
result:
ok 1 number(s): "12"
Test #5:
score: 0
Accepted
time: 0ms
memory: 111524kb
input:
2 21
output:
2
result:
ok 1 number(s): "2"
Test #6:
score: 0
Accepted
time: 0ms
memory: 111180kb
input:
3 233
output:
10
result:
ok 1 number(s): "10"
Test #7:
score: 0
Accepted
time: 3ms
memory: 110896kb
input:
3 666
output:
54
result:
ok 1 number(s): "54"
Test #8:
score: -100
Time Limit Exceeded
input:
1000000 3333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333...