fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MOD = 1000000007;
  5.  
  6. int add(int a, int b) {
  7.     return (a + b) % MOD;
  8. }
  9.  
  10. int solve_subtask_2(string S, int N, int M, int K) {
  11.     int totalWays = 0;
  12.     int questionMarks = count(S.begin(), S.end(), '?');
  13.  
  14.     for (int mask = 0; mask < (1 << questionMarks); ++mask) {
  15.         string temp = S;
  16.         int idx = 0;
  17.         for (int i = 0; i < N; ++i) {
  18.             if (temp[i] == '?') {
  19.                 temp[i] = (mask & (1 << idx)) ? 'A' : 'B';
  20.                 idx++;
  21.             }
  22.         }
  23.  
  24.         int immunity = 0;
  25.         for (int i = M; i <= N; ++i) {
  26.             bool same = true;
  27.             for (int j = 0; j < M - 1; ++j) {
  28.                 if (temp[i - j - 1] != temp[i - j - 2]) {
  29.                     same = false;
  30.                     break;
  31.                 }
  32.             }
  33.             if (same) immunity++;
  34.         }
  35.  
  36.         if (immunity == K) totalWays = add(totalWays, 1);
  37.     }
  38.  
  39.     return totalWays;
  40. }
  41.  
  42. int solve_subtask_4(string S, int N) {
  43.     string pattern1 = string("ABABABABABABABAB").substr(0, N);
  44.     string pattern2 = string("BABABABABABABABA").substr(0, N);
  45.  
  46.     auto matchesPattern = [&](string &pattern) {
  47.         for (int i = 0; i < N; ++i) {
  48.             if (S[i] != '?' && S[i] != pattern[i]) return false;
  49.         }
  50.         return true;
  51.     };
  52.  
  53.     int count = 0;
  54.     if (matchesPattern(pattern1)) count = add(count, 1);
  55.     if (matchesPattern(pattern2)) count = add(count, 1);
  56.  
  57.     return count;
  58. }
  59.  
  60. int solve_subtask_5(string S, int N, int M) {
  61.     vector<vector<int>> dp(N + 1, vector<int>(2, 0));
  62.     dp[0][0] = dp[0][1] = 1;
  63.  
  64.     for (int i = 1; i <= N; ++i) {
  65.         for (int c = 0; c <= 1; ++c) {
  66.             dp[i][c] = 0;
  67.             for (int j = max(0, i - M); j < i; ++j) {
  68.                 bool valid = true;
  69.                 for (int k = j; k < i; ++k) {
  70.                     if (S[k] != '?' && S[k] != (c ? 'B' : 'A')) {
  71.                         valid = false;
  72.                         break;
  73.                     }
  74.                 }
  75.                 if (valid) dp[i][c] = add(dp[i][c], dp[j][c ^ 1]);
  76.             }
  77.         }
  78.     }
  79.  
  80.     return add(dp[N][0], dp[N][1]);
  81. }
  82.  
  83. int main() {
  84.     int N, M, K;
  85.     cin >> N >> M >> K;
  86.     string S;
  87.     cin >> S;
  88.  
  89.     if (N <= 20) {
  90.         cout << solve_subtask_2(S, N, M, K) << endl;
  91.     } else if (M == 2 && K == 0) {
  92.         cout << solve_subtask_4(S, N) << endl;
  93.     } else if (K == 0) {
  94.         cout << solve_subtask_5(S, N, M) << endl;
  95.     } else {
  96.         cout << 0 << endl; 
  97.     }
  98.  
  99.     return 0;
  100. }
  101.  
Success #stdin #stdout 0.01s 5260KB
comments (?)
stdin
copy 
5 4 1
?????
stdout
copy 
4
https://ideone.com/LPJ9Vn
language:
C++14 (clang 8.0)
created:
7 days 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!