Advertisement
prestige

KPI12_G

Aug 21st, 2012
217
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.37 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3. #include <vector>
  4. #include <string>
  5. using namespace std;
  6. const int mod = (1e+9)+7;
  7. int n;
  8. string s;
  9. long long sum = 0;
  10. vector<int> z_function (string s) {
  11.     int n = (int) s.length();
  12.     vector<int> z (n);
  13.     for (int i=1, l=0, r=0; i<n; ++i) {
  14.         if (i <= r)
  15.             z[i] = min (r-i+1, z[i-l]);
  16.         while (i+z[i] < n && s[z[i]] == s[i+z[i]])
  17.             ++z[i];
  18.         if (i+z[i]-1 > r)
  19.             l = i,  r = i+z[i]-1;
  20.     }
  21.     return z;
  22. }
  23. //long long binpow (long long a, long long n) {
  24. //  long long res = 1;
  25. //  while (n) {
  26. //      if (n & 1)
  27. //          res = ((res % mod) * (a % mod)) % mod;
  28. //      a = ((a % mod) * (a % mod)) % mod;
  29. //      n >>= 1;
  30. //  }
  31. //  return res;
  32. //}
  33. long long binpow (long long a, long long n) {
  34.     if (n == 0)
  35.         return 1ll;
  36.     if (n % 2 == 1)
  37.         return (binpow (a, n-1) * (a % mod)) % mod;
  38.     else {
  39.         long long b = binpow (a, n/2);
  40.         return (b * b) % mod;
  41.     }
  42. }
  43. int main() {
  44.     cin >> s;
  45.     int len = s.length();
  46.     for (int i = 1; i < len; i++) {
  47.         int t = 0;
  48.         if(len % i ==0) {
  49.             string b;
  50.             for (int j = 0; j < i; j++) {
  51.                 b += s[j]; 
  52.             }
  53.             b += "#" + s;
  54.             vector<int> a = z_function(b);
  55.             for (int j = 0; j < len / i; j++) {
  56.                 if(a[i + j * i + 1] == i) {
  57.                     t++;
  58.                 }
  59.             }
  60.         }
  61.         if(t == (len / i))
  62.             sum = (sum + binpow(26, i) - 1ll) % mod;
  63.         else
  64.             sum = (sum + binpow(26, i)) % mod;
  65.     }
  66.     cout << sum % mod;
  67.     return 0;
  68. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement