fork(3) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define rep(i,a,n) for (int i=a;i<n;i++)
  4. #define per(i,a,n) for (int i=n-1;i>=a;i--)
  5. #define pb push_back
  6. #define mp make_pair
  7. #define all(x) (x).begin(),(x).end()
  8. #define fi first
  9. #define se second
  10. #define SZ(x) ((int)(x).size())
  11. typedef vector<int> VI;
  12. typedef long long ll;
  13. typedef pair<int,int> PII;
  14. const ll mod=1000000007;
  15. ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
  16. ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
  17. // head
  18.  
  19. const int N=310,O=300;
  20. int s[N],n,cnt,t[N];
  21. char c[N];
  22.  
  23. bool checkff(int *s) {
  24. 	rep(i,1,n+1) if (s[i]<0) return 0;
  25. 	return s[n]==0;
  26. }
  27. bool checkbf() {
  28. 	if (checkff(s)) return 1;
  29. 	rep(j,1,n+1) rep(k,j,n+1) {
  30. 		rep(i,1,n+1) {
  31. 			t[i]=t[i-1]+((i>=j&&i<=k)?(-1):1)*(s[i]-s[i-1]);
  32. 		}
  33. 		if (checkff(t)) {
  34. 			return 1;
  35. 		}
  36. 	}
  37. 	return 0;
  38. }
  39.  
  40. bool check() {
  41. 	if (n%2!=0) return 0;
  42. 	int prem=0,sufm=s[n],pj=-1,pk=-1;
  43. 	rep(i,1,n+1) if (s[i]<0) {
  44. 		pj=i;
  45. 		break;
  46. 	} else prem=max(prem,s[i]);
  47. 	per(i,1,n+1) if (s[i]<s[n]) {
  48. 		pk=i;
  49. 		break;
  50. 	} else sufm=max(sufm,s[i]);
  51. 	if (pj==-1&&pk==-1) return 1;
  52. 	if (pj==-1) {
  53. 		per(i,0,n+1) {
  54. 			if (2*s[i]==2*sufm-s[n]) return 1;
  55. 			if (s[i]>2*sufm-s[n]) return 0;
  56. 		}
  57. 		assert(0);
  58. 	}
  59. 	if (pk==-1) {
  60. 		rep(i,1,n+1) {
  61. 			if (2*s[i]==2*prem+s[n]) return 1;
  62. 			if (s[i]>2*prem) return 0;
  63. 		}
  64. 	}
  65. 	rep(i,1,n+1) printf("%d ",s[i]); puts("");
  66. 	printf("%d %d\n",pj,pk);
  67. 	assert(pj<pk);
  68. 	rep(i,pj,pk+1) if (s[i]>min(2*prem,2*sufm-s[n])) return 0;
  69. 	return 1;
  70. }
  71.  
  72. int ret;
  73. int dp1[N][N];
  74. int dpl[N][2*N][N],dpr[N][2*N][N],rel[N][2*N],rer[N][2*N];
  75. void upd(int &a,int b) {
  76. 	a+=b; if (a>=mod) a-=mod;
  77. }
  78. void solve1() {
  79. 	dp1[0][0]=1;
  80. 	rep(i,0,n) rep(j,0,i+1) if (dp1[i][j]) {
  81. 		if (c[i+1]=='('||c[i+1]=='x') upd(dp1[i+1][j+1],dp1[i][j]);
  82. 		if ((c[i+1]==')'||c[i+1]=='x')&&j>0) upd(dp1[i+1][j-1],dp1[i][j]);
  83. 	}
  84. 	upd(ret,dp1[n][0]);
  85. }
  86. void solve2() {
  87. 	rep(i,0,n+2) rep(j,-i,i+1) rel[i][j+O]=rer[i][j+O]=0;
  88. //	rep(gmx,-1,n+1) {
  89. 	rep(gmx,-1,n+1) {
  90. 		rep(i,0,n+2) rep(j,-i,i+1) rep(sta,0,3) dpl[i][j+O][sta]=dpr[i][j+O][sta]=0;
  91. 		dpl[0][0+O][0>=gmx]=1;
  92. 		rep(i,0,n) for (int j=-i;j<=i;j+=2) rep(sta,0,3) if (dpl[i][j+O][sta]) {
  93. 			int val=dpl[i][j+O][sta];
  94. 			if (c[i+1]=='('||c[i+1]=='x') {
  95. 				if (sta==0) {
  96. 					if (2*(j+1)>=gmx) upd(dpl[i+1][j+1+O][1],val);
  97. 					else upd(dpl[i+1][j+1+O][0],val);
  98. 				} else if (sta==1) {
  99. 					upd(dpl[i+1][j+1+O][1],val);
  100. 				} else {
  101. 					if (j+1==gmx) upd(rel[i+1][O+gmx],val);
  102. 					if (j+1<gmx) upd(dpl[i+1][j+1+O][2],val);
  103. 				}
  104. 			}
  105. 			if (c[i+1]==')'||c[i+1]=='x') {
  106. 				if (sta==0) {
  107. 					if (j>0) upd(dpl[i+1][j-1+O][0],val);
  108. 				} else if (sta==1) {
  109. 					if (j>0) upd(dpl[i+1][j-1+O][1],val);
  110. 					else {
  111. 						if (gmx==-1) upd(rel[i+1][O+gmx],val);
  112. 						else upd(dpl[i+1][j-1+O][2],val);
  113. 					}
  114. 				} else {
  115. 					upd(dpl[i+1][j-1+O][2],val);
  116. 				}
  117. 			}
  118. 		}
  119. 		dpr[0][0+O][0>=gmx]=1;
  120. 		rep(i,0,n) for (int j=-i;j<=i;j+=2) rep(sta,0,3) if (dpr[i][j+O][sta]) {
  121. 			int val=dpr[i][j+O][sta];
  122. 			if (c[n-i]==')'||c[n-i]=='x') {
  123. 				if (sta==0) {
  124. 					if (2*(j+1)>=gmx) upd(dpr[i+1][j+1+O][1],val);
  125. 					else upd(dpr[i+1][j+1+O][0],val);
  126. 				} else if (sta==1) {
  127. 					upd(dpr[i+1][j+1+O][1],val);
  128. 				} else {
  129. 					if (j+1==gmx) upd(rer[i+1][O+gmx],val);
  130. 					if (j+1<=gmx) upd(dpr[i+1][j+1+O][2],val);
  131. 				}
  132. 			}
  133. 			if (c[n-i]=='('||c[n-i]=='x') {
  134. 				if (sta==0) {
  135. 					if (j>0) upd(dpr[i+1][j-1+O][0],val);
  136. 				} else if (sta==1) {
  137. 					if (j>0) upd(dpr[i+1][j-1+O][1],val);
  138. 					else {
  139. 						if (gmx==-1) upd(rer[i+1][O+gmx],val);
  140. 						upd(dpr[i+1][j-1+O][2],val);
  141. 					}
  142. 				} else {
  143. 					upd(dpr[i+1][j-1+O][2],val);
  144. 				}
  145. 			}
  146. 		}
  147. 	}
  148. //	printf("%d\n",rel[5][1+O]);
  149. 	rep(gmx,-1,n+1) rep(i,1,n) rep(sn,-n,n+1) if (gmx-sn>=-1&&gmx-sn<=n-i)
  150. 		upd(ret,(ll)rel[i][gmx+O]*rer[n-i][gmx-sn+O]%mod);
  151. }
  152.  
  153. int pdl[N][2*N][6];
  154. void solve3() {
  155. 	for (int gmx=0;gmx<=n;gmx++) for (int sn=-2;sn>=-n;sn-=2) if (gmx+gmx-sn<=n) {
  156. 		rep(i,0,n+1) for (int j=-i;j<=i;j+=2) rep(sta,0,6) pdl[i][j+O][sta]=0;
  157. 		pdl[0][O][gmx==0]=1;
  158. 		rep(i,0,n) for (int j=max(-i,sn+(i&1));j<=i&&j<=sn+n-i;j+=2) rep(sta,0,6) if (pdl[i][j+O][sta]) {
  159. 			int val=pdl[i][j+O][sta];
  160. 			if (c[i+1]=='('||c[i+1]=='x') {
  161. 				if (sta==0) {
  162. 					if (j+1==gmx) upd(pdl[i+1][j+1+O][1],val);
  163. 					if (j+1<gmx) upd(pdl[i+1][j+1+O][0],val);
  164. 				} else if (sta==1) {
  165. 					if (j+1<=gmx) upd(pdl[i+1][j+1+O][1],val);
  166. 				} else if (sta==2) {
  167. 					if (j+1<=2*gmx) upd(pdl[i+1][j+1+O][2],val);
  168. 				} else	if (sta==3) {
  169. 					if (j+1==gmx) upd(pdl[i+1][j+1+O][4],val);
  170. 					if (j+1<gmx) upd(pdl[i+1][j+1+O][3],val);
  171. 				} else if (sta==4) {
  172. 					if (j+1<=gmx) upd(pdl[i+1][j+1+O][4],val);
  173. 				} else if (sta==5) {
  174. 					upd(pdl[i+1][j+1+O][5],val);
  175. 				}
  176. 			}
  177. 			if (c[i+1]==')'||c[i+1]=='x') {
  178. 				if (j-1<sn) continue;
  179. 				int w=0;
  180. 				if ((j-1)==gmx+sn/2&&sta<3) w=3;
  181. 				if (sta==0) {
  182. 					if (j>0) upd(pdl[i+1][j-1+O][w],val);
  183. 				} else if (sta==1) {
  184. 					if (j>0) upd(pdl[i+1][j-1+O][1+w],val);
  185. 					else upd(pdl[i+1][j-1+O][2+w],val);
  186. 				} else if (sta==2) {
  187. 					upd(pdl[i+1][j-1+O][2+w],val);
  188. 				} else if (sta==3) {
  189. 					if (j>0) upd(pdl[i+1][j-1+O][3],val);
  190. 				} else if (sta==4) {
  191. 					if (j>0) upd(pdl[i+1][j-1+O][4],val);
  192. 					else upd(pdl[i+1][j-1+O][5],val);
  193. 				} else {
  194. 					upd(pdl[i+1][j-1+O][5],val);
  195. 				}
  196. 			}
  197. 		}
  198. 		upd(ret,pdl[n][sn+O][5]);
  199. 	}
  200. 	for (int gmx=0;gmx<=n;gmx++) for (int sn=-2;sn>=-n;sn-=2) if (gmx+gmx-sn<=n) {
  201. 		rep(i,0,n+1) for (int j=-i;j<=i;j+=2) rep(sta,0,6) pdl[i][j+O][sta]=0;
  202. 		pdl[0][O][gmx==0]=1;
  203. 		rep(i,0,n) for (int j=max(-i,sn+(i&1));j<=i&&j<=sn+n-i;j+=2) rep(sta,0,6) if (pdl[i][j+O][sta]) {
  204. 			int val=pdl[i][j+O][sta];
  205. 			if (c[n-i]==')'||c[n-i]=='x') {
  206. 				if (sta==0) {
  207. 					if (j+1==gmx) upd(pdl[i+1][j+1+O][1],val);
  208. 					if (j+1<gmx) upd(pdl[i+1][j+1+O][0],val);
  209. 				} else if (sta==1) {
  210. 					if (j+1<=gmx) upd(pdl[i+1][j+1+O][1],val);
  211. 				} else if (sta==2) {
  212. 					if (j+1<=2*gmx) upd(pdl[i+1][j+1+O][2],val);
  213. 				} else	if (sta==3) {
  214. 					if (j+1==gmx) upd(pdl[i+1][j+1+O][4],val);
  215. 					if (j+1<gmx) upd(pdl[i+1][j+1+O][3],val);
  216. 				} else if (sta==4) {
  217. 					if (j+1<=gmx) upd(pdl[i+1][j+1+O][4],val);
  218. 				} else if (sta==5) {
  219. 					upd(pdl[i+1][j+1+O][5],val);
  220. 				}
  221. 			}
  222. 			if (c[n-i]=='('||c[n-i]=='x') {
  223. 				if (j-1<sn) continue;
  224. 				int w=0;
  225. 				if ((j-1)==gmx+sn/2&&sta<3) w=3;
  226. 				if (sta==0) {
  227. 					if (j>0) upd(pdl[i+1][j-1+O][w],val);
  228. 				} else if (sta==1) {
  229. 					if (j>0) upd(pdl[i+1][j-1+O][1+w],val);
  230. 					else upd(pdl[i+1][j-1+O][2+w],val);
  231. 				} else if (sta==2) {
  232. 					upd(pdl[i+1][j-1+O][2+w],val);
  233. 				} else if (sta==3) {
  234. 					if (j>0) upd(pdl[i+1][j-1+O][3],val);
  235. 				} else if (sta==4) {
  236. 					if (j>0) upd(pdl[i+1][j-1+O][4],val);
  237. 					else upd(pdl[i+1][j-1+O][5],val);
  238. 				} else {
  239. 					upd(pdl[i+1][j-1+O][5],val);
  240. 				}
  241. 			}
  242. 		}
  243. 		upd(ret,pdl[n][sn+O][5]);
  244. 	}
  245. }
  246.  
  247. int main() {
  248. 	scanf("%d",&n);
  249. 	scanf("%s",c+1);
  250. //	rep(i,1,n+1) c[i]='x';
  251. 	if (n%2!=0) { puts("0"); return 0; }
  252. 	solve1();
  253. //	printf("%d\n",ret); ret=0;
  254. 	solve2();
  255. //	printf("%d\n",ret); ret=0;
  256. 	solve3();
  257. //	printf("%d\n",ret); ret=0;
  258. 	printf("%d\n",ret);
  259. }
  260.  
Success #stdin #stdout 0s 4500KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/gbMlux
language:
C++14 (gcc 8.3)
created:
6 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!