Fshl0

Bovine Genetics

Jun 7th, 2021
624
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 1e5 + 9;
  6. const int M = 5;
  7. const int MOD = 1e9 + 7;
  8.  
  9. int dp[N][M][M][M];
  10.  
  11. int main () {
  12.     string s, deCode = "AGCT";
  13.     cin >> s;
  14.     int n = s.length();
  15.     for (int n = 0; n < 4; n++)
  16.         for (int l = 0; l < 4; l++)
  17.             if (s[0] == '?' || s[0] == deCode[l])
  18.                 dp[0][n][l][l] = 1;
  19.     for (int k = 1; k < s.length(); k++) {
  20.         for (int m2 = 0; m2 < 4; m2++) {
  21.             if (s[k] == '?' || s[k] == deCode[m2]) {
  22.                 for (int n = 0; n < 4; n++) {
  23.                     for (int l = 0; l < 4; l++) {
  24.                         for (int m = 0; m < 4; m++) {
  25.                             if (m != m2) {
  26.                                 dp[k][n][l][m2] += dp[k - 1][n][l][m];
  27.                                 dp[k][n][l][m2] %= MOD;
  28.                             }
  29.  
  30.                             if (n == m) {
  31.                                 dp[k][l][m2][m2] += dp[k - 1][n][l][m];
  32.                                 dp[k][l][m2][m2] %= MOD;
  33.                             }
  34.                         }
  35.                     }
  36.                 }
  37.             }
  38.         }
  39.     }
  40.     int res = 0;
  41.     for (int l = 0; l < 4; l++) {
  42.         for (int m = 0; m < 4; m++) {
  43.             res += dp[s.length() - 1][m][l][m];
  44.             res %= MOD;
  45.         }
  46.     }
  47.     cout << res << "\n";
  48.     return 0;
  49. }
  50.  
RAW Paste Data