fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5.  
  6. const int N = 2005;
  7. const int MOD = 111539786;
  8.  
  9. int n, k, nodes = 0;
  10. int trie[N][2], fail[N], dp[2][N];
  11. bool bad[N];
  12.  
  13. void insert(string s) {
  14.     int u = 0;
  15.     for (int i = 0; i < (int)s.size(); i++) {
  16.         int c = s[i] - '0';
  17.         if (!trie[u][c]) trie[u][c] = ++nodes;
  18.         u = trie[u][c];
  19.     }
  20.     bad[u] = true;
  21. }
  22.  
  23. void build() {
  24.     queue<int> q;
  25.     for (int c = 0; c < 2; c++)
  26.         if (trie[0][c]) q.push(trie[0][c]);
  27.     while (!q.empty()) {
  28.         int u = q.front(); q.pop();
  29.         for (int c = 0; c < 2; c++) {
  30.             if (trie[u][c]) {
  31.                 fail[trie[u][c]] = trie[fail[u]][c];
  32.                 bad[trie[u][c]] |= bad[fail[trie[u][c]]];
  33.                 q.push(trie[u][c]);
  34.             } else trie[u][c] = trie[fail[u]][c];
  35.         }
  36.     }
  37. }
  38.  
  39. void solve() {
  40.     cin >> n >> k;
  41.     for (int i = 0; i < k; i++) {
  42.         string s; cin >> s;
  43.         insert(s);
  44.     }
  45.     build();
  46.     int cur = 0;
  47.     dp[cur][0] = 1;
  48.     for (int i = 0; i < n; i++)  {
  49.         int nxt = cur ^ 1;
  50.         memset(dp[nxt], 0, sizeof dp[nxt]);
  51.         for (int u = 0; u <= nodes; u++) {
  52.             if (dp[cur][u] == 0) continue;
  53.             for (int c = 0; c < 2; c++) {
  54.                 int v = trie[u][c];
  55.                 if (!bad[v]) {
  56.                     dp[nxt][v] += dp[cur][u];
  57.                     if (dp[nxt][v] >= MOD) dp[nxt][v] -= MOD;
  58.                 }
  59.             }
  60.         }
  61.         cur = nxt;
  62.     }
  63.     int ans = 0;
  64.     for (int u = 0; u <= nodes; u++) {
  65.         ans += dp[cur][u];
  66.         if (ans >= MOD) ans -= MOD;
  67.     }
  68.     cout << ans << '\n';
  69. }
  70.  
  71. int main() {
  72.     ios_base::sync_with_stdio(false); cin.tie(NULL);
  73.  
  74.     #define TASK "DNASEQ"
  75.     if (fopen(TASK".INP", "r")) {
  76.         freopen(TASK".INP", "r", stdin);
  77.         freopen(TASK".OUT", "w", stdout);
  78.     }
  79.  
  80.     int tests = 1; // cin >> tests;
  81.     while (tests--) solve();
  82.  
  83.     #ifndef LOCAL
  84.     cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  85.     #endif
  86.  
  87.     return 0;
  88. }
  89.  
Success #stdin #stdout #stderr 0.01s 5320KB
comments (?)
stdin
copy 
2 2
00
10
stdout
copy 
2
stderr
copy 
Time elapsed: 0.004952 s.
https://ideone.com/d4RLMN
language:
C++14 (gcc 8.3)
created:
1 day 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!