fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define int long long
  5. using namespace std;
  6. const long long oo=1e18;
  7. const int mod=1e9+7;
  8. const int base=31;
  9. int Test=1;
  10. void home()
  11. {
  12.     if(fopen("main.inp","r")) 
  13.     freopen("main.inp","r",stdin),
  14.     freopen("main.out","w",stdout);
  15. }
  16. bool bit(int mask,int i){return (mask>>i)&1;}
  17. int n,kq;
  18. string s[100005];
  19. int mu[1000006],hX[1000006],hN[1000006];
  20. void BuildHash(string s)
  21. {
  22.     hX[0]=hN[s.size()]=0;
  23.     for(int i=1;i<s.size();i++)hX[i]=(hX[i-1]*base+(s[i]-'a'+1))%mod;
  24.     for(int i=s.size()-1;i>=1;i--)hN[i]=(hN[i+1]*base+(s[i]-'a'+1))%mod;
  25. }
  26. int GetX(int j,int i)
  27. {
  28.     return (hX[i]-hX[j-1]*mu[i-j+1]%mod+mod)%mod;
  29. }
  30. int GetN(int j,int i)
  31. {
  32.     return (hN[j]-hN[i+1]*mu[i-j+1]%mod+mod)%mod;
  33. }
  34. bool PalinCheck(int j,int i)
  35. {
  36.     return GetN(j,i)==GetX(j,i);
  37. }
  38. struct Trie
  39. {
  40.     struct Node
  41.     {
  42.         Node *child[26];int en,pal;
  43.         Node()
  44.         {
  45.             for(int i=0;i<26;i++)child[i]=NULL;
  46.             en=0;pal=0;
  47.         }
  48.     };
  49.     Node *root;Trie(){root=new Node();}
  50.     void Insert(string s)
  51.     {
  52.         Node *p=root;
  53.         for(int i=s.size()-1;i>=1;i--)
  54.         {
  55.             int c=s[i]-'a';
  56.             if(p->child[c]==NULL)p->child[c]=new Node();
  57.             p=p->child[c];
  58.             if(i>1)p->pal+=PalinCheck(1,i-1);
  59.         }
  60.         p->en++;
  61.     }
  62.     void CntPalin(string s)
  63.     {
  64.         Node *p=root;
  65.         for(int i=1;i<s.size();i++)
  66.         {
  67.             int c=s[i]-'a';
  68.             if(p->child[c]==NULL)return;
  69.             p=p->child[c];
  70.             kq+=p->en*PalinCheck(i+1,s.size()-1);
  71.         }
  72.         kq+=p->pal;
  73.     }
  74. }*T;
  75. void Tcmduc_VOI26()
  76. {
  77.     cin>>n;
  78.     T=new Trie();
  79.     mu[0]=1;for(int i=1;i<=1000000;i++)mu[i]=(mu[i-1]*base)%mod;
  80.     for(int i=1;i<=n;i++)
  81.     {
  82.         cin>>s[i];s[i]=' '+s[i];BuildHash(s[i]);
  83.         T->Insert(s[i]);
  84.     }
  85.     for(int i=1;i<=n;i++)
  86.     {
  87.         BuildHash(s[i]);
  88.         T->CntPalin(s[i]);
  89.         if(PalinCheck(1,s[i].size()-1))kq--;
  90.         //cout<<kq<<'\n';
  91.     }
  92.     cout<<kq;
  93. }
  94. signed main()
  95. {
  96.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);home();
  97.     while(Test--)Tcmduc_VOI26();
  98.     return 0;
  99. }
Success #stdin #stdout 0.01s 14744KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/TVsUWL
language:
C++14 (gcc 8.3)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!