fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define fi first
  5. #define se second
  6. #define MP make_pair
  7. #define PB push_back
  8. #define ll long long
  9. #define pii pair<int, int>
  10. #define SZ(a) int(a.size())
  11. #define ALL(a) a.begin(), a.end()
  12. #define MS(a, v) memset(a, v, sizeof a)
  13. #define REP(i, n) for(int i = 0; i < n; ++ i)
  14. #define FOR(i, a, b) for(int i = (a); i <= (b); ++ i)
  15. #define FOD(i, a, b) for(int i = (a); i >= (b); -- i)
  16. #define TSun(TZ) freopen(TZ".inp", "r", stdin), freopen(TZ".out", "w", stdout)
  17.  
  18. template<class X, class Y>
  19.         bool maximize(X & x, const Y & y){
  20.                 if(x < y){
  21.                         x = y;
  22.                         return true;
  23.                 }
  24.                 else return false;
  25.         }
  26.  
  27. template<class X, class Y>
  28.         bool minimize(X & x, const Y & y){
  29.                 if(x > y){
  30.                         x = y;
  31.                         return true;
  32.                 }
  33.                 else return false;
  34.         }
  35.  
  36. const int MAXN = 4004;
  37. const int MOD = 1e9 + 7;
  38. const ll INF = 1e18;
  39.  
  40. int n;
  41. string T;
  42.  
  43. namespace sub1{
  44.  
  45.         int dd[21], res;
  46.  
  47.         void backtrack(int i){
  48.                 if(i > n){
  49.  
  50.                         int cnt = 0;
  51.  
  52.                         FOR(L, 1, n){
  53.  
  54.                                 if(cnt < 0) break;
  55.  
  56.                                 int x = cnt;
  57.  
  58.                                 FOR(R, L, n){
  59.                                         x += - dd[R];
  60.                                         if(x < 0) break;
  61.                                         int idx = R + 1, dem = x;
  62.                                         while(idx <= n){
  63.                                                 dem += dd[idx];
  64.                                                 if(dem < 0) break;
  65.                                                 ++ idx;
  66.                                         }
  67.  
  68. //                                        if(idx > n && dem == 0){
  69. //                                                FOR(id, 1, n) cout << dd[id] << " ";
  70. //                                                cout << " " << L << " " << R << "\n";
  71. //                                        }
  72.  
  73.                                         res += idx > n && dem == 0;
  74.                                 }
  75.  
  76.                                 cnt += dd[L];
  77.                         }
  78.  
  79.                         return;
  80.                 }
  81.  
  82.                 if(T[i] == '('){
  83.                         dd[i] = 1;
  84.                         backtrack(i + 1);
  85.                 }
  86.  
  87.                 else if(T[i] == ')'){
  88.                         dd[i] = -1;
  89.                         backtrack(i + 1);
  90.                 }
  91.                 else{
  92.                         FOR(v, -1, 1)if(v){
  93.                                 dd[i] = v;
  94.                                 backtrack(i + 1);
  95.                         }
  96.                 }
  97.         }
  98.  
  99.         void solve(void){
  100.                 backtrack(1);
  101.                 cout << res;
  102.         }
  103. }
  104.  
  105. int f[3][MAXN][MAXN / 2];
  106.  
  107. void add(int &a, int b){
  108.         a += b;
  109.         if(a >= MOD) a -= MOD;
  110. }
  111.  
  112. void solve(void){
  113.         cin >> n >> T;
  114.         T = " " + T;
  115.  
  116. //        if(n <= 20)
  117. //                return sub1 :: solve();
  118.  
  119.         f[0][0][0] = 1;
  120.         FOR(i, 1, n){
  121.                 if(T[i] == '('){
  122.                         REP(x, n / 2){
  123.                                 add(f[0][i][x + 1], f[0][i - 1][x]);
  124.                                 add(f[1][i][x], f[0][i - 1][x + 1]);
  125.                                 add(f[1][i][x], f[1][i - 1][x + 1]);
  126.                                 add(f[2][i][x + 1], f[1][i - 1][x]);
  127.                                 add(f[2][i][x + 1], f[2][i - 1][x]);
  128.                         }
  129.                 }
  130.                 else if(T[i] == ')'){
  131.                         FOR(x, 1, n / 2){
  132.                                 add(f[0][i][x - 1], f[0][i - 1][x]);
  133.                                 add(f[1][i][x], f[0][i - 1][x - 1]);
  134.                                 add(f[1][i][x], f[1][i - 1][x - 1]);
  135.                                 add(f[2][i][x - 1], f[1][i - 1][x]);
  136.                                 add(f[2][i][x - 1], f[2][i - 1][x]);
  137.                         }
  138.                 }
  139.                 else{
  140.                         REP(x, n / 2){
  141.                                 add(f[0][i][x + 1], f[0][i - 1][x]);
  142.                                 add(f[1][i][x], f[0][i - 1][x + 1]);
  143.                                 add(f[1][i][x], f[1][i - 1][x + 1]);
  144.                                 add(f[2][i][x + 1], f[1][i - 1][x]);
  145.                                 add(f[2][i][x + 1], f[2][i - 1][x]);
  146.                         }
  147.                         FOR(x, 1, n / 2){
  148.                                 add(f[0][i][x - 1], f[0][i - 1][x]);
  149.                                 add(f[1][i][x], f[0][i - 1][x - 1]);
  150.                                 add(f[1][i][x], f[1][i - 1][x - 1]);
  151.                                 add(f[2][i][x - 1], f[1][i - 1][x]);
  152.                                 add(f[2][i][x - 1], f[2][i - 1][x]);
  153.                         }
  154.                 }
  155.         }
  156.         cout << (f[2][n][0] + f[1][n][0]) % MOD;
  157. }
  158.  
  159. int main(void){
  160.  
  161.         ios_base :: sync_with_stdio(0);
  162.         cin.tie(0); cout.tie(0);
  163.  
  164.         #define TaZinh "BRACKET"
  165.  
  166.         if(fopen(TaZinh".inp", "r"))
  167.                 TSun(TaZinh);
  168.  
  169.         int Sun = 1;
  170. //        cin >> Sun;
  171.         REP(love, Sun) solve();
  172.  
  173.         return 0;
  174. }
  175.  
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/IJXn0g
language:
C++ (gcc 8.3)
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!