Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

KPI12_G

By: prestige on Aug 21st, 2012  |  syntax: C++  |  size: 1.37 KB  |  hits: 52  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  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. }
create a new version of this paste RAW Paste Data