Advertisement
Georgiy031

Untitled

Oct 7th, 2020
86
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.17 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. typedef long long ll;
  5. typedef unsigned long long ull;
  6. #define all(x) x.begin(), x.end()
  7. #define rall(x) x.rbegin(), x.rend()
  8. #define endl '\n'
  9. #define boostIO() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  10. ll gcd(ll a, ll b) { return (b == 0 ? a : gcd(b, a % b)); }
  11.  
  12. signed main() {
  13.     int n, count = 0;
  14.     ll mod = 1e9 + 7;
  15.     string s;
  16.     cin >> n >> s;
  17.     for (auto ch : s) if (ch == '?') ++count;
  18.     vector<vector<vector<ll>>> dp(n + 1, vector<vector<ll>>(4, vector<ll>(4)));
  19.     vector<ll> v(n + 1, 1);
  20.     for (int i = 1; i <= n; ++i) {
  21.         v[i] = (v[i - 1] * 3) % mod;
  22.     }
  23.  
  24.     dp[0][0][0] = 1;
  25.     for (int i = 0; i < n; ++i) {
  26.         for (int j = 0; j <= 3; ++j) {
  27.             for (int k = 0; k <= 3; ++k) {
  28.                 if (dp[i][j][k]) {
  29.                     dp[i + 1][j][k] += dp[i][j][k];
  30.                     dp[i + 1][j][k] %= mod;
  31.                     if (j < 3 && (s[i] == '?' || s[i] - 'a' == j)) {
  32.                         int nk = (s[i] == '?' ? k + 1 : k);
  33.                         dp[i + 1][j + 1][nk] += dp[i][j][k];
  34.                         dp[i + 1][j + 1][nk] %= mod;
  35.                     }
  36.                 }
  37.             }
  38.         }
  39.     }
  40.     ll ans = 0;
  41.     for (int i = 0; i <= 3; ++i) {
  42.         if (count >= i) {
  43.             ans += (dp[n][3][i] * v[count - i]) % mod;
  44.             ans %= mod;
  45.         }
  46.     }
  47.     cout << ans;
  48. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement