QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#591356 | #5440. P-P-Palindrome | pengpeng_fudan# | WA | 675ms | 75152kb | C++23 | 3.1kb | 2024-09-26 15:32:22 | 2024-09-26 15:32:23 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll =long long;
const int N=1000010;
map<pair<ll,ll>,int> mp;
map<pair<ll,ll>,pair<pair<ll,ll>,int>> mz;
const ll p1=1331,p2=13331,M1=1000000007,M2=998244353;
ll h1[N],h2[N];
pair<ll,ll> hsh[N];
pair<ll,ll> get(pair<ll,ll> p,pair<pair<ll,ll>,int> q){
return {(p.first*h1[q.second]%M1+q.first.first)%M1,(p.second*h2[q.second]%M2+q.first.second)%M2};
}
pair<ll,ll> get(int l,int r){
return {
((hsh[r].first-((l==0?0:hsh[l-1].first)*h1[r-l+1]%M1))%M1+M1)%M1,
((hsh[r].second-((l==0?0:hsh[l-1].second)*h2[r-l+1]%M2))%M2+M2)%M2
};
}
struct pam{
int ch[N][26];
int fail[N],len[N];
int cnt,tot;
int pz[N];
int get_pre(string& s,int ct,int wei){
while(wei-len[ct]<=0||s[wei-len[ct]-1]!=s[wei]){
ct=fail[ct];
}
return ct;
}
void palid_tr(string& s){
cnt=tot=1;
fail[0]=1,fail[1]=0,len[0]=0,len[1]=-1;
fill(ch[0],ch[0]+26,0),fill(ch[1],ch[1]+26,0);
int sz=s.size();
for(int i=0;i<sz;i++){
hsh[i].first=((i==0?0:hsh[i-1].first)*p1%M1+s[i]-'a'+1)%M1;
hsh[i].second=((i==0?0:hsh[i-1].second)*p2%M2+s[i]-'a'+1)%M2;
}
for(int i=0;i<sz;i++){
int ct=get_pre(s,tot,i);
if(!ch[ct][s[i]-'a']) {
cnt++;
fill(ch[cnt],ch[cnt]+26,0);
len[cnt]=len[ct]+2;
pz[cnt]=i;
fail[cnt]=ch[get_pre(s,fail[ct],i)][s[i]-'a'];
ch[ct][s[i]-'a']=cnt;
}
tot=ch[ct][s[i]-'a'];
}
vector<vector<int>> re(tot+1);
for(int i=0;i<=tot;i++){
if(i!=1) re[fail[i]].push_back(i);
}
auto dfs=[&](auto self,int u)->void {
if(u!=0&&u!=1){
pair<ll,ll> get_hs=get(pz[u]-len[u]+1,pz[u]);
if(mz.find(get_hs)==mz.end()){
mp[get_hs]=1;
mz[get_hs]={get_hs,len[u]};
mz[get(get_hs,{get_hs,len[u]})]={get_hs,len[u]};
}
else{
pair<pair<ll,ll>,int> hp=mz[get_hs];
mp[hp.first]=max(mp[hp.first],len[u]/hp.second);
mz[get(get_hs,hp)]=hp;
}
}
for(auto i:re[u]){
self(self,i);
}
};
dfs(dfs,0);
}
};
pam pm;
void solve(void) {
int n;
cin>>n;
for(int i=1;i<=n;i++){
string s;
cin>>s;
pm.palid_tr(s);
}
ll ans=0;
for(auto i:mp) {
// cerr<<i.second<<' '<<i.first.second<<' '<<i.first.first<<'\n';
ans=ans+1ll*i.second*i.second;
}
cout<<ans<<'\n';
}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
h1[0]=h2[0]=1;
for(int i=1;i<=1000000;i++){
h1[i]=h1[i-1]*p1%M1;
h2[i]=h2[i-1]*p2%M2;
}
int _ = 1;
while (_--) solve();
return 0;
}
/*
2
aaaa
aaa
*/
详细
Test #1:
score: 100
Accepted
time: 6ms
memory: 29168kb
input:
2 aaaa aaa
output:
16
result:
ok 1 number(s): "16"
Test #2:
score: 0
Accepted
time: 9ms
memory: 28940kb
input:
3 abaaa abbbba bbbaba
output:
28
result:
ok 1 number(s): "28"
Test #3:
score: 0
Accepted
time: 6ms
memory: 27964kb
input:
1 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
output:
15130
result:
ok 1 number(s): "15130"
Test #4:
score: 0
Accepted
time: 9ms
memory: 28160kb
input:
3 aaaaaaaaaaaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbbbbbbbbbb bababababababaabababababa
output:
1282
result:
ok 1 number(s): "1282"
Test #5:
score: 0
Accepted
time: 168ms
memory: 54852kb
input:
5 ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff...
output:
3600000000
result:
ok 1 number(s): "3600000000"
Test #6:
score: 0
Accepted
time: 168ms
memory: 59196kb
input:
5 wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...
output:
3600000000
result:
ok 1 number(s): "3600000000"
Test #7:
score: 0
Accepted
time: 675ms
memory: 73728kb
input:
3 abbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbab...
output:
133586
result:
ok 1 number(s): "133586"
Test #8:
score: 0
Accepted
time: 630ms
memory: 71868kb
input:
3 abbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbabab...
output:
118967
result:
ok 1 number(s): "118967"
Test #9:
score: 0
Accepted
time: 619ms
memory: 75152kb
input:
3 bbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabb...
output:
114444
result:
ok 1 number(s): "114444"
Test #10:
score: 0
Accepted
time: 619ms
memory: 72896kb
input:
3 abbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbabab...
output:
115321
result:
ok 1 number(s): "115321"
Test #11:
score: 0
Accepted
time: 623ms
memory: 72544kb
input:
3 azzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazaz...
output:
131825
result:
ok 1 number(s): "131825"
Test #12:
score: -100
Wrong Answer
time: 7ms
memory: 30536kb
input:
3 yazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbyb...
output:
5
result:
wrong answer 1st numbers differ - expected: '6', found: '5'