Advertisement
Guest User

Untitled

a guest
Jun 18th, 2019
147
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.33 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define maxn 1000010
  5. const int mod=1e9+7;
  6. const int c=26;
  7. char s[maxn];
  8. int f[maxn];
  9. int n,k;
  10. ll pw(ll a,int n)
  11. {
  12. ll res=1;
  13. while(n)
  14. {
  15. if(n&1)res=res*a%mod;
  16. a=a*a%mod,n>>=1;
  17. }
  18. return res;
  19. }
  20. ll INV(ll a){return pw(a,mod-2);}
  21. void fail()
  22. {
  23. f[0]=-1;
  24. for(int i=1;i<n;i++)
  25. {
  26. int j=f[i-1];
  27. while(j>=0 && s[j+1]!=s[i])j=f[j];
  28. if(s[j+1]==s[i])f[i]=j+1;
  29. else f[i]=j;
  30. }
  31. }
  32. int main()
  33. {
  34. scanf("%d%d",&n,&k);
  35. scanf("%s",s);
  36. fail();
  37. // for(int i=0;i<n;i++)printf("%d ",f[i]);puts("");
  38. // printf("n = %d, k = %d\n",n,k);
  39. ll ans=0;
  40. int cur=n-1;
  41. while(cur!=-1)
  42. {
  43. if(2*n-(cur+1)>k)break;
  44. // printf("cur = %d\n",cur);
  45. ans++,cur=f[cur];
  46. }
  47. if(k>=2*n)//1+c+...+c^m=(c^(m+1)-1)/(c-1)
  48. {
  49. int m=k-2*n;
  50. ll tmp=pw(c,m+1);
  51. tmp=(tmp-1+mod)%mod;
  52. tmp=tmp*INV(c-1)%mod;
  53. ans=(ans+tmp)%mod;
  54. }
  55. printf("%lld\n",ans);
  56. return 0;
  57. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement