fork(4) download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7.  
  8. #define fi first
  9. #define se second
  10. #define mp make_pair
  11. #define pb push_back
  12. #define fbo find_by_order
  13. #define ook order_of_key
  14.  
  15. typedef long long ll;
  16. typedef pair<int,int> ii;
  17. typedef vector<int> vi;
  18. typedef long double ld; 
  19. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
  20. typedef set<int>::iterator sit;
  21. typedef map<int,int>::iterator mit;
  22. typedef vector<int>::iterator vit;
  23.  
  24. const int MOD = 1e9 + 7;
  25.  
  26. ll dp[511][511];
  27. //solve for [l, r]
  28. string s;
  29.  
  30. ll g(char a, char b)
  31. {
  32. 	int cnt = 0;
  33. 	if((a == '(' || a == '?') && (b == ')' || b == '?')) cnt++;
  34. 	if((a == '[' || a == '?') && (b == ']' || b == '?')) cnt++;
  35. 	return cnt;
  36. }
  37.  
  38. ll f(int l, int r) //solves for [l, r)
  39. {
  40. 	if(l>r) return 0;
  41. 	if(l == r) return 1;
  42. 	if(dp[l][r] != -1) return dp[l][r];
  43. 	ll ans = 0;
  44. 	for(int i = l + 1; i < r; i += 2)
  45. 	{
  46. 		ans = (ans + (g(s[l],s[i])*(f(l+1,i)*f(i+1,r))%MOD)%MOD)%MOD;
  47. 	}
  48. 	dp[l][r] = ans;
  49. 	dp[l][r]%=MOD;
  50. 	if(dp[l][r]<0) dp[l][r]+=MOD;
  51. 	return ans;
  52. }
  53.  
  54. int main()
  55. {
  56. 	ios_base::sync_with_stdio(0); cin.tie(0);
  57. 	cin>>s;
  58. 	int n = int(s.length());
  59. 	memset(dp, -1, sizeof(dp));
  60. 	cout<<f(0,n)<<'\n';
  61. }
  62.  
Success #stdin #stdout 0s 5504KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/afbiNF
language:
C++14 (gcc 8.3)
created:
7 years 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!