题解 p3449 【[poi2006]pal

#define int long long
#define inf 0x3f3f3f3f
#define N 2000002
#define hash HASH
#define mod 1000000007
#define base 131
using namespace std;
int n,m,hash[N],len[N],ch[N][26],tot,po[N],w[N],ans;
string s[N];
int (string s){
    int res=0,len=s.length();
    for (int i=0;i<len;++i)res=(res*base+s[i]-'a')%mod;
    return res;
}
inline int read(){
    int x=0,w=0;char ch=getchar();
    while (!isdigit(ch))w|=ch=='-',ch=getchar();
    while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return w?-x:x;
}
void build(string s,int id){
    int len=s.length(),now=0;
    for (int i=0;i<len;++i){
        int v=s[i]-'a';
        if (!ch[now][v])ch[now][v]=++tot;
        now=ch[now][v];
    }
    w[now]=id;
}
void query(string ss,int id){
    int le=ss.length(),now=0;
    for (int i=0;i<le;++i){
        int v=ss[i]-'a';
        now=ch[now][v];
        if (w[now]&&w[now]!=id){
            if ((hash[w[now]]*po[len[id]]%mod+hash[id])%mod==(hash[id]*po[len[w[now]]]%mod+hash[w[now]])%mod){
                ++ans;
            }
        }
    }
}
signed main(){
    n=read();po[0]=1;
    for (int i=1;i<=200000;++i)po[i]=po[i-1]*base%mod;
    for (int i=1;i<=n;++i){
        len[i]=read();cin>>s[i];
        build(s[i],i);
        hash[i]=calc(s[i]);
    }
    for (int i=1;i<=n;++i)
        query(s[i],i);
    cout<<ans*2+n;    
    return 0;
}