fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4.  
  5. using namespace std;
  6.  
  7. const int MOD = 1000000007;
  8.  
  9. // Function to compute the number of ways s_i and s_j can be matched
  10. int ways(char s_i, char s_j) {
  11.     // Possible matching pairs: '()', '[]', '{}'
  12.     if (s_i == '?' && s_j == '?') {
  13.         return 3; // '()', '[]', '{}'
  14.     } else if (s_i == '?') {
  15.         // s_i can be '(', '[', '{' to match s_j
  16.         if (s_j == ')') return 1; // s_i must be '('
  17.         if (s_j == ']') return 1; // s_i must be '['
  18.         if (s_j == '}') return 1; // s_i must be '{'
  19.         return 0;
  20.     } else if (s_j == '?') {
  21.         // s_j can be ')', ']', '}' to match s_i
  22.         if (s_i == '(') return 1; // s_j must be ')'
  23.         if (s_i == '[') return 1; // s_j must be ']'
  24.         if (s_i == '{') return 1; // s_j must be '}'
  25.         return 0;
  26.     } else {
  27.         // Both are specific characters
  28.         if ((s_i == '(' && s_j == ')') ||
  29.             (s_i == '[' && s_j == ']') ||
  30.             (s_i == '{' && s_j == '}'))
  31.             return 1;
  32.         else
  33.             return 0;
  34.     }
  35. }
  36.  
  37. int main() {
  38.     int N;
  39.     string s;
  40.     cin >> N;
  41.     cin >> s;
  42.  
  43.     // Edge case: if N is odd, no correct bracket sequence is possible
  44.     if (N % 2 != 0) {
  45.         cout << 0 << endl;
  46.         return 0;
  47.     }
  48.  
  49.     // Initialize DP table
  50.     vector<vector<int>> dp(N + 1, vector<int>(N + 1, 0));
  51.  
  52.     // Base case: empty substrings
  53.     for (int i = 0; i <= N; ++i) {
  54.         dp[i][i] = 1;
  55.     }
  56.  
  57.     // DP over substring lengths
  58.     for (int len = 1; len <= N; ++len) {
  59.         for (int i = 0; i + len <= N; ++i) {
  60.             int j = i + len;
  61.  
  62.             // Check for matching pair at positions i and j - 1
  63.             int w = ways(s[i], s[j - 1]);
  64.             if (w > 0) {
  65.                 dp[i][j] = (dp[i][j] + (1LL * dp[i + 1][j - 1] * w) % MOD) % MOD;
  66.             }
  67.  
  68.             // Split the substring into two parts and sum up the ways
  69.             for (int k = i + 1; k < j; ++k) {
  70.                 dp[i][j] = (dp[i][j] + (1LL * dp[i][k] * dp[k][j]) % MOD) % MOD;
  71.             }
  72.         }
  73.     }
  74.  
  75.     // Output the result modulo 1e9 + 7
  76.     cout << dp[0][N] << endl;
  77.  
  78.     return 0;
  79. }
Success #stdin #stdout 0s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/YcchcL
language:
C++ (gcc 8.3)
created:
18 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!