fork download
copy 
  1. //NiceDuck
  2. #include "bits/stdc++.h"
  3. typedef long long ll;
  4. using namespace std;
  5. #define FILE "000"
  6. #define foru(i,a,b) for(int i=(int)(a); i<=(int)(b); ++i)
  7. #define ford(i,a,b) for(int i=(int)(a); i>=(int)(b); --i)
  8. #define fastio ios_base::sync_with_stdio(0);cin.tie(0);
  9. #define pb push_back
  10. #define fi first
  11. #define se second
  12. #define el "\n"
  13. #define MASK(i) (1LL<<(i))
  14. #define BIT(i,j) (((i)>>(j))&1)
  15. #define TIME 1.0*clock()/CLOCKS_PER_SEC
  16. #define LOG 20
  17.  
  18. const ll MAX=5e4+4;
  19. int n,q;
  20. string str,rev;
  21.  
  22. const ll BASE=67, MOD1=1e9+7, MOD2=1561023067;
  23. struct Hash
  24. {
  25.     vector<ll> h1,h2,p1,p2;
  26.     Hash(string s)
  27.     {
  28.         int l=s.size()-1;
  29.         h1.assign(l+2,0);
  30.         h2.assign(l+2,0);
  31.         p1.assign(l+2,0);
  32.         p2.assign(l+2,0);
  33.         p1[0]=p2[0]=1;
  34.         foru(i,1,l)
  35.         {
  36.             p1[i]=(p1[i-1]*BASE)%MOD1;
  37.             p2[i]=(p2[i-1]*BASE)%MOD2;
  38.             h1[i]=(h1[i-1]*BASE + (s[i]-'a'))%MOD1;
  39.             h2[i]=(h2[i-1]*BASE + (s[i]-'a'))%MOD2;
  40.         }
  41.     }
  42.     pair<ll,ll> getHash(int l, int r)
  43.     {
  44.         ll x=(h1[r]-h1[l-1]*p1[r-l+1]+MOD1*MOD1)%MOD1, y=(h2[r]-h2[l-1]*p2[r-l+1]+MOD2*MOD2)%MOD2;
  45.         return make_pair(x,y);
  46.     }
  47. };
  48.  
  49. ll f[5003][5003];
  50. //void pre()
  51. //{
  52. //    foru(i,1,n) f[i][i]=1;
  53. //    foru(i,1,n-1)
  54. //    {
  55. //        f[i][i+1]=2;
  56. //        if(str[i]==str[i+1]) f[i][i+1]++;
  57. //    }
  58. //    ford(l,n-2,1)
  59. //    {
  60. //        foru(r,l+2,n)
  61. //        {
  62. //            f[l][r]=f[l][r-1]+f[l+1][r]-f[l+1][r-1];
  63. //            int l1=n-r+1, r1=n-l+1;
  64. //            pair<ll,ll> pa1=hs1.getHash(l,r), pa2=hs2.getHash(l1,r1);
  65. //            if(pa1.fi==pa2.fi && pa1.se==pa2.se) ++f[l][r];
  66. //        }
  67. //    }
  68. //}
  69.  
  70. int main()
  71. {
  72.     fastio
  73.     if(fopen(FILE ".inp","r"))
  74.     {
  75.         freopen(FILE ".inp","r",stdin); freopen(FILE ".out","w",stdout);
  76.     }
  77.     cin>>str;
  78.     n=str.size();
  79.     ford(i,str.size()-1,0) rev+=str[i];
  80.     str=" "+str;
  81.     rev=" "+rev;
  82.     Hash hs1(str), hs2(rev);
  83.     foru(i,1,n) f[i][i]=1;
  84.     foru(i,1,n-1)
  85.     {
  86.         f[i][i+1]=2;
  87.         if(str[i]==str[i+1]) f[i][i+1]++;
  88.     }
  89.     ford(l,n-2,1)
  90.     {
  91.         foru(r,l+2,n)
  92.         {
  93.             f[l][r]=f[l][r-1]+f[l+1][r]-f[l+1][r-1];
  94.             int l1=n-r+1, r1=n-l+1;
  95.             pair<ll,ll> pa1=hs1.getHash(l,r), pa2=hs2.getHash(l1,r1);
  96.             if(pa1.fi==pa2.fi && pa1.se==pa2.se) ++f[l][r];
  97.         }
  98.     }
  99.     cin>>q;
  100.     while(q--)
  101.     {
  102.         int l,r; cin>>l>>r;
  103.         cout<<f[l][r]<<el;
  104.     }
  105.  
  106.     return 0;
  107. }
  108.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/8vLhlI
language:
C++14 (gcc 8.3)
created:
2 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!