fork download 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define mod 1000000007ll
  4. using namespace std;
  5. int f[505][505], g[505][505];
  6. string s;
  7. int get(int i, int j) {
  8.     if (s[i] == '(') return s[j] == ')' || s[j] == '?';
  9.     if (s[i] == '[') return s[j] == ']' || s[j] == '?';
  10.     if (s[i] == '{') return s[j] == '}' || s[j] == '?';
  11.     if (s[i] == '?')
  12.         return s[j] == '?' ? 3 : (s[j] == ')' || s[j] == ']' || s[j] == '}');
  13.     return 0;
  14. }
  15. signed main() {
  16.     ios_base::sync_with_stdio(false);
  17.     cin.tie(NULL);    cout.tie(NULL);
  18.     cin >> s;
  19.     int n = s.size();
  20.     s = " " + s;
  21.     for (int i = 1; i < s.size(); i++) f[i][i + 1] = g[i][i + 1] = get(i, i + 1);
  22.     for (int sz = 4; sz <= n; sz += 2) {
  23.         for (int i = 1; i <= n - sz + 1; i++) {
  24.             int j = sz + i - 1;
  25.             f[i][j] = g[i][j] = get(i, j) * g[i + 1][j - 1];
  26.             for (int k = i + 2; k < j; k++)
  27.                 g[i][j] += f[i][k - 1] * g[k][j], g[i][j] %= mod;
  28.             f[i][j] %= mod;
  29.         }
  30.     }
  31.     cout << g[1][n];
  32. }
  33.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/yHU5sJ
language:
C++14 (clang 8.0)
created:
6 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!