QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#321485 | #7876. Cyclic Substrings | Endline | ML | 165ms | 350280kb | C++14 | 2.4kb | 2024-02-04 20:30:03 | 2024-02-04 20:30:04 |
Judging History
answer
/*
* Author: Endline
* Time: 2024/02/04 17:25:18
* File: String-N.cpp
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
using ll=long long;
const int MAXN=6000002;
const int mod=998244353;
template<typename _Tp>inline void Add(_Tp&x,int y){x=x+y>=mod?x+y-mod:x+y;}
int n;
string str;
struct PlalindromeAutomaton
{
int ans;
string str;
int pcnt=1,las,ecnt;
int f[23][MAXN];
int ch[MAXN][10],fail[MAXN],len[MAXN],cnt[MAXN],head[MAXN],ed[MAXN],val[MAXN];
struct TreeEdge
{
int v,nxt;
}e[MAXN];
inline void addedge(int u,int v)
{
e[++ecnt]={v,head[u]};
head[u]=ecnt;
}
inline int getfail(int p,int id)
{
while(id-len[p]-1<1||str[id-len[p]-1]!=str[id])p=fail[p];
return p;
}
inline void extend(int c,int id)
{
int p=getfail(las,id);
if(!ch[p][c])
{
pcnt++;
ed[pcnt]=id;
fail[pcnt]=ch[getfail(fail[p],id)][c];
len[pcnt]=len[p]+2;
ch[p][c]=pcnt;
}
cnt[ch[p][c]]++;
las=ch[p][c];
return;
}
inline void insert(string s)
{
str=' '+s;
for(int i=1;i<=s.size();i++)
extend(str[i]-'0',i);
return;
}
inline void init()
{
fail[0]=1,len[1]=-1;
}
void dfs(int u)
{
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].v;
dfs(v);
Add(val[u],val[v]);
}
}
inline int work()
{
for(int i=2;i<=pcnt;i++)
f[0][i]=fail[i];
for(int i=1;(1<<i)<=pcnt;i++)
for(int j=0;j<=pcnt;j++)
f[i][j]=f[i-1][f[i-1][j]];
for(int i=2;i<=pcnt;i++)
{
int p=i;
for(int j=22;j>=0;j--)
if(ed[i]-len[f[j][p]]+1<=n)p=f[j][p];
Add(val[i],cnt[i]);
Add(val[fail[p]],mod-cnt[i]);
}
for(int i=2;i<=pcnt;i++)
addedge(fail[i],i);
dfs(0);
for(int i=2;i<=pcnt;i++)
if(len[i]<=n)Add(ans,1ll*val[i]*val[i]%mod*len[i]%mod);
return ans;
}
}Pt;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
cin>>str;str=str+str;
Pt.init();
Pt.insert(str);
printf("%d\n",Pt.work());
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 4044kb
input:
5 01010
output:
39
result:
ok 1 number(s): "39"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3776kb
input:
8 66776677
output:
192
result:
ok 1 number(s): "192"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3768kb
input:
1 1
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 1ms
memory: 4044kb
input:
2 22
output:
12
result:
ok 1 number(s): "12"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
2 21
output:
2
result:
ok 1 number(s): "2"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
3 233
output:
10
result:
ok 1 number(s): "10"
Test #7:
score: 0
Accepted
time: 1ms
memory: 4116kb
input:
3 666
output:
54
result:
ok 1 number(s): "54"
Test #8:
score: 0
Accepted
time: 165ms
memory: 350280kb
input:
1000000 3333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333...
output:
496166704
result:
ok 1 number(s): "496166704"
Test #9:
score: -100
Memory Limit Exceeded
input:
3000000 2222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222...
output:
890701718