fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5.  
  6. const int N = 65;
  7.  
  8. int n, m;
  9. string s;
  10. int pi[N], nxt[N][2];
  11. ll dp[N][N];
  12.  
  13. void solve() {
  14.     cin >> n >> s;
  15.     m = (int)s.size();
  16.     for (int i = 1; i < m; i++) {
  17.         int j = pi[i - 1];
  18.         while (j > 0 && s[i] != s[j]) j = pi[j - 1];
  19.         if (s[i] == s[j]) j++;
  20.         pi[i] = j;
  21.     }
  22.     for (int i = 0; i <= m; i++)
  23.         for (int c = 0; c < 2; c++) {
  24.             if (c == (s[i] - '0')) nxt[i][c] = i + 1;
  25.             else if (i > 0) nxt[i][c] = nxt[pi[i - 1]][c];
  26.         }
  27.     ll res = 0;
  28.     for (int k = 0; k < m; k++) {
  29.         memset(dp, 0, sizeof dp);
  30.         dp[0][k] = 1;
  31.         for (int i = 0; i < n; i++) {
  32.             for (int u = 0; u < m; u++) {
  33.                 for (int c = 0; c < 2; c++) {
  34.                     int v = nxt[u][c];
  35.                     if (v < m) dp[i + 1][v] += dp[i][u];
  36.                 }
  37.             }
  38.         }
  39.         res += dp[n][k];
  40.     }
  41.     cout << (1LL << n) - res << "\n";
  42. }
  43.  
  44. int main() {
  45.     ios_base::sync_with_stdio(0); cin.tie(0);
  46.  
  47.     #define TASK "PLASMID"
  48.     if (fopen(TASK".INP", "r")) {
  49.         freopen(TASK".INP", "r", stdin);
  50.         freopen(TASK".OUT", "w", stdout);
  51.     }
  52.  
  53.     int tests = 1; // cin >> tests;
  54.     while (tests--) solve();
  55.  
  56.     #ifdef LOCAL
  57.     cerr << "\nTime elapsed: " << clock() << " ms.\n";
  58.     #endif
  59.     return 0;
  60. }
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
3
00
stdout
copy 
4
https://ideone.com/9kytbX
ĐTQG Cà Mau 2025 - Bài 2 - Mật mã di truyền
language:
C++14 (gcc 8.3)
created:
3 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!