結果

問題 No.464 PPAP
ユーザー mugen_1337
提出日時 2020-12-18 22:15:53
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,473 ms / 2,000 ms
コード長 6,253 bytes
コンパイル時間 2,303 ms
コンパイル使用メモリ 219,676 KB
最終ジャッジ日時 2025-01-17 03:08:08
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#define ALL(x) begin(x),end(x)
#define rep(i,n) for(int i=0;i<(n);i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define mod 998244353
using ll=long long;
const int INF=1000000000;
const ll LINF=1001002003004005006ll;
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")


struct IOSetup{
    IOSetup(){
        cin.tie(0);
        ios::sync_with_stdio(0);
        cout<<fixed<<setprecision(12);
    }
} iosetup;
 
template<typename T>
ostream &operator<<(ostream &os,const vector<T>&v){
    for(int i=0;i<(int)v.size();i++) os<<v[i]<<(i+1==(int)v.size()?"":" ");
    return os;
}
template<typename T>
istream &operator>>(istream &is,vector<T>&v){
    for(T &x:v)is>>x;
    return is;
}

struct PalindromicTree{
    struct node{
        map<char,int> link;// link aba -> xabax
        int len,cnt,idx;// s[idx, idx+len)に1つこの回文がある
        int suffix_link;
        node(){}
        node(int len,int cnt,int idx,int suffix_link):len(len),cnt(cnt),idx(idx),suffix_link(suffix_link){}
    };
 
    vector<node> v;// 0:(-1), 1: (0)
    int n,ptr;
 
    PalindromicTree(){}
    PalindromicTree(const string &s):v(2),n(2),ptr(1){
        v[0]=node(-1,0,-1,0);v[1]=node(0,0,-1,0);
        for(int i=0;i<(int)s.size();i++) process(s,i);
        build_freq();
    }
 
    bool process(const string &s,int pos){
        int cur=ptr;// link parent
        while(true){
            int rev=pos-v[cur].len-1;
            if(rev>=0 and s[rev]==s[pos]) break;
            cur=v[cur].suffix_link;
        }
        if(v[cur].link.count(s[pos])){
            ptr=v[cur].link[s[pos]];
            v[ptr].cnt++;
            return false;
        }
        ptr=n++;
 
        v.emplace_back(v[cur].len+2,1,pos-v[cur].len-1,-1);
        v[cur].link[s[pos]]=ptr;// link
        if(v[ptr].len==1){
            v[ptr].suffix_link=1;
            return true;
        }
 
        while(true){
            cur=v[cur].suffix_link;
            int rev=pos-v[cur].len-1;
            if(rev>=0 and s[rev]==s[pos]){
                v[ptr].suffix_link=v[cur].link[s[pos]];
                break;
            }
        }
        return true;
    }
    // DAGをトポソ
    vector<int> calc_ord(){
        vector<int> ret;
        ret.emplace_back(0);
        ret.emplace_back(1);
        for(int i=0;i<(int)ret.size();i++)for(auto &p:v[ret[i]].link) ret.emplace_back(p.second);
        return ret;
    }
    void build_freq(){
        auto ord=calc_ord();
        // 一番長い回文にしかcnt+=1をしていないので，linkで集約する
        for(int i=(int)ord.size()-1;i>=0;i--) v[v[ord[i]].suffix_link].cnt+=v[ord[i]].cnt;
    }
    // nodeのindexに対し，stringを構築．重い
    string id_to_string(int idx){
        if(idx<2) return "";
        string ret="";
        function<bool(int)> dfs=[&](int cur){
            if(cur==idx) return true;
            for(auto to:v[cur].link){
                if(dfs(to.second)){
                    ret.push_back(to.first);
                    return true;
                }
            }
            return false;
        };
        bool odd_len=dfs(0);
        if(!odd_len) dfs(1);
        string rev=ret;
        if(odd_len) rev.pop_back();
        reverse(begin(rev),end(rev));
        return ret+rev;
    }
    int count_unique(){return n-2;}
    int size(){return n;}
    node operator[](const int &k){return v[k];}
};

using ull=unsigned long long;
struct RollingHash{
    using ull=unsigned long long;
    using uint128=__uint128_t;
    static const ull MOD=(1ull<<61ull)-1;
    vector<ull>hashed,power;
    const ull base;
 
    static inline ull add(ull a,ull b){if((a+=b)>=MOD)a-=MOD;return a;}
    static inline ull mul(ull a,ull b){uint128 c=(uint128)a*b;return add(c>>61,c&MOD);}
    static inline ull generate_base(){
        mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
        uniform_int_distribution<ull>rand(1,RollingHash::MOD-1);
        return rand(mt);
    }
    RollingHash()=default;
    RollingHash(const string &s,ull base):base(base){
        int sz=(int)s.size();
        hashed.assign(sz+1,0);
        power.assign(sz+1,0);
        power[0]=1;
        for(int i=0;i<sz;i++){
            power[i+1]=mul(power[i],base);
            hashed[i+1]=add(mul(hashed[i],base),s[i]);
        }
    }
    template<typename T>
    RollingHash(const vector<T>&s,ull base):base(base){
        int sz=(int)s.size();
        hashed.assign(sz+1,0);
        power.assign(sz+1,0);
        power[0]=1;
        for(int i=0;i<sz;i++){
            power[i+1]=mul(power[i],base);
            hashed[i+1]=add(mul(hashed[i],base),s[i]);
        }
    }
    // hash[l,r)
    ull get(int l,int r)const{
        return add(hashed[r],MOD-mul(hashed[l],power[r-l]));
    }
    ull concat(ull hash1,ull hash2,int hash2len)const{
        return add(mul(hash1,power[hash2len]),hash2);
    }
    int lcp(const RollingHash &b,int l1,int r1,int l2,int r2)const{
        assert(b.base==base);
        int len=min(r1-l1,r2-l2);
        int lw=0,hi=len+1;
        while(hi-lw>1){
            int mid=(lw+hi)/2;
            if(get(l1,l1+mid)==b.get(l2,l2+mid))lw=mid;
            else hi=mid;
        }
        return lw;
    }
};

signed main(){
    string s;cin>>s;
    int n=(int)s.size();

    PalindromicTree pt(s); // yossha

    auto base=RollingHash::generate_base();
    RollingHash rh(s,base);

    vector<ll> l(n+1,0),r(n+1,0);

    for(int i=2;i<pt.n;i++){
        int li=pt[i].len;
        ull p1=rh.get(pt[i].idx,pt[i].idx+li);

        if(rh.get(n-li,n)==p1) r[n-li]++;
        if(p1!=rh.get(0,li)) continue;

        for(int j=2;j<pt.n;j++){
            int lj=pt[j].len;
            if(li+lj>n) continue;
            ull p2=rh.get(pt[j].idx,pt[j].idx+lj);
            if(rh.get(li,li+lj)==p2) l[li+lj]++;
        }
    }
    ll res=0,sum=0;
    for(int i=n;i>=0;i--){
        res+=sum*l[i];
        sum+=r[i];
    }
    cout<<res<<"\n";
    return 0;
}
0