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=1e4+4;
  19. int n,l;
  20. string str;
  21.  
  22. const ll BASE=311, MOD1=1e9+7, MOD2=1561023067;
  23. ll h1[MAX],h2[MAX],p1[MAX],p2[MAX];
  24. void buildHash()
  25. {
  26.     p1[0]=p2[0]=1;
  27.     foru(i,1,l)
  28.     {
  29.         p1[i]=(p1[i-1]*BASE)%MOD1;
  30.         p2[i]=(p2[i-1]*BASE)%MOD2;
  31.         h1[i]=(h1[i-1]*BASE + (int)(str[i]))%MOD1;
  32.         h2[i]=(h2[i-1]*BASE + (int)(str[i]))%MOD2;
  33.     }
  34. }
  35. pair<ll,ll> getHash(int L, int R)
  36. {
  37.     ll x=(h1[R]-h1[L-1]*p1[R-L+1]+MOD1*MOD1)%MOD1;
  38.     ll y=(h2[R]-h2[L-1]*p2[R-L+1]+MOD2*MOD2)%MOD2;
  39.     return make_pair(x,y);
  40. }
  41. map<pair<ll,ll>,ll> mp;
  42.  
  43. ll pw(ll x, ll y)
  44. {
  45.     ll res=1;
  46.     while(y>0)
  47.     {
  48.         if(y&1) res=(res*x)%MOD1;
  49.         x=(x*x)%MOD1;
  50.         y>>=1;
  51.     }
  52.     return res;
  53. }
  54.  
  55. int main()
  56. {
  57.     fastio
  58.     if(fopen(FILE ".inp","r"))
  59.     {
  60.         freopen(FILE ".inp","r",stdin); freopen(FILE ".out","w",stdout);
  61.     }
  62.     cin>>str; cin>>n;
  63.     l=str.size();
  64.     str=" "+str;
  65.     buildHash();
  66.     foru(i,1,l)
  67.     {
  68.         ford(j,i,1)
  69.         {
  70.             pair<ll,ll> tmp=getHash(j,i);
  71.             mp[tmp]++;
  72.         }
  73.     }
  74.     ll ans=0;
  75.     for(pair<pair<ll,ll>,ll> pa:mp)
  76.     {
  77.         ll x=pa.se;
  78.         ans=(ans+pw(x,n))%MOD1;
  79.     }
  80.     cout<<ans;
  81.  
  82.     return 0;
  83. }
  84.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/5dWVGO
language:
C++14 (gcc 8.3)
created:
7 hours 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!