QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#591356#5440. P-P-Palindromepengpeng_fudan#WA 675ms75152kbC++233.1kb2024-09-26 15:32:222024-09-26 15:32:23

Judging History

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

  • [2024-09-26 15:32:23]
  • 评测
  • 测评结果:WA
  • 用时:675ms
  • 内存:75152kb
  • [2024-09-26 15:32:22]
  • 提交

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'