QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#388110 | #6891. String and GCD | Ecec243 | AC ✓ | 3420ms | 253588kb | C++23 | 2.1kb | 2024-04-13 11:59:02 | 2024-04-13 11:59:02 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
vi pi(const string &s)
{
vi p(sz(s));
rep(i, 1, sz(s))
{
int g = p[i - 1];
while (g && s[i] != s[g])
g = p[g - 1];
p[i] = g + (s[i] == s[g]);
}
return p;
}
const int M = 998244353;
const int MAXN = 1000000;
vector<int> dv[MAXN + 1];
int phi[MAXN + 1];
void calculatePhi()
{
rep(i, 0, MAXN + 1) phi[i] = i & 1 ? i : i / 2;
for (int i = 3; i < MAXN + 1; i += 2)
if (phi[i] == i)
for (int j = i; j < MAXN + 1; j += i)
phi[j] -= phi[j] / i;
}
void init()
{
calculatePhi();
for (int i = 1; i <= MAXN; i++)
{
for (int j = i; j <= MAXN; j += i)
{
dv[j].push_back(i);
}
}
}
int hist[MAXN + 1];
void dfs(int now, vector<vector<int>> &adj, vi &kmp, vector<int> &ans)
{
for (int j : dv[now + 1])
{
ans[now] = (ans[now] + 1LL * hist[j] * phi[j]) % M;
}
for (int j : dv[now + 1])
{
hist[j]++;
}
for (int u : adj[now])
{
dfs(u, adj, kmp, ans);
}
for (int j : dv[now + 1])
{
hist[j]--;
}
}
void solve()
{
string s;
cin >> s;
int n = s.size();
vi kmp = pi(s);
vector<vector<int>> adj(n);
for (int i = 0; i < n; i++)
{
if (kmp[i] != 0)
{
adj[kmp[i] - 1].push_back(i);
}
}
vector<int> ans(n);
for (int i = 0; i < n; i++)
{
if (kmp[i] == 0)
{
dfs(i, adj, kmp, ans);
}
}
int res = 1;
for (int i : ans)
{
res = (1LL * res * (i + 1)) % M;
}
cout << res << '\n';
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
init();
int t;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3420ms
memory: 253588kb
input:
10 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
348588201 444875250 645157594 69295643 479125431 754799284 363702774 250095339 288773558 250829868
result:
ok 10 lines