fork download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. long long count_occurrences(const string& S, const string& P) {
  9.     int n = S.length();
  10.     int m = P.length();
  11.     if (m > n) return 0;
  12.  
  13.     vector<int> pi(m, 0);
  14.     for (int i = 1, j = 0; i < m; ++i) {
  15.         while (j > 0 && P[i] != P[j]) j = pi[j - 1];
  16.         if (P[i] == P[j]) j++;
  17.         pi[i] = j;
  18.     }
  19.  
  20.     long long count = 0;
  21.     for (int i = 0, j = 0; i < n; ++i) {
  22.         while (j > 0 && S[i] != P[j]) j = pi[j - 1];
  23.         if (S[i] == P[j]) j++;
  24.         if (j == m) {
  25.             count++;
  26.             j = pi[m - 1];
  27.         }
  28.     }
  29.     return count;
  30. }
  31.  
  32. long long count_boundary_occurrences(const string& A, const string& B, const string& P) {
  33.     int m = P.length();
  34.     if (m <= 1) return 0;
  35.  
  36.     int lenA = min((int)A.length(), m - 1);
  37.     int lenB = min((int)B.length(), m - 1);
  38.  
  39.     string boundary_str = A.substr(A.length() - lenA) + B.substr(0, lenB);
  40.     return count_occurrences(boundary_str, P);
  41. }
  42.  
  43. int main() {
  44.     ios_base::sync_with_stdio(false);
  45.     cin.tie(NULL);
  46.  
  47.     string P;
  48.     int n;
  49.  
  50.     if (!(cin >> P >> n)) return 0;
  51.  
  52.     int m = P.length();
  53.  
  54.     vector<string> F = {"", "b", "a"};
  55.  
  56.     if (n <= 2) {
  57.         cout << count_occurrences(F[n], P) << "\n";
  58.         return 0;
  59.     }
  60.  
  61.     int k = 2;
  62.     while (k < n && F[k].length() < 2 * m) {
  63.         k++;
  64.         F.push_back(F[k - 1] + F[k - 2]);
  65.     }
  66.  
  67.     vector<long long> C(n + 1, 0);
  68.  
  69.     for (int i = 1; i <= k; ++i) {
  70.         C[i] = count_occurrences(F[i], P);
  71.     }
  72.  
  73.     if (k == n) {
  74.         cout << C[n] << "\n";
  75.         return 0;
  76.     }
  77.  
  78.     long long cross1 = count_boundary_occurrences(F[k], F[k - 1], P);
  79.  
  80.     long long cross2 = count_boundary_occurrences(F[k] + F[k - 1], F[k], P);
  81.  
  82.     for (int i = k + 1; i <= n; ++i) {
  83.         long long cross = ((i - k) % 2 == 1) ? cross1 : cross2;
  84.         C[i] = C[i - 1] + C[i - 2] + cross;
  85.     }
  86.  
  87.     cout << C[n] << "\n";
  88.  
  89.     return 0;
  90. }
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
aba
200
stdout
copy 
-5968922811834797816
https://ideone.com/7Vd3Jv
language:
C++14 (gcc 8.3)
created:
17 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!