1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69
| #include<iostream> #include<cstdio> #include<algorithm> #include<queue> #include<cstring> #include<stack> #define mod 998244353LL #define mem(ss) memset(ss,0,sizeof(ss)) #define ll long long #define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std; ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);} inline int read(){int data=0;char ch=0;while (ch<'0' || ch>'9') ch=getchar();while (ch>='0' && ch<='9') data=data*10+ch-'0',ch=getchar();return data;} ll lowspeed(ll a,ll b,ll p){ll cur=a,ans=0;while(b){if(b&1) ans=(ans+cur)%p;cur=(cur+cur)%p;b>>=1;}return ans%p;} ll speed(ll a,ll b,ll p){ll cur=a,ans=1;while(b){if(b&1) ans=lowspeed(ans,cur,p)%p;cur=lowspeed(cur,cur,p)%p;b>>=1;}return ans%p;} string s; int a[120]; int dfs(int l,int r,int val){ if(r==l+1){ return 1; } int sum=0,a1=0,a2=0; for(int i=l+1;i<r;i++){ if(a[i]==val+1){ if(a1==0){ a1=i; } else{ a2=i; sum+=dfs(a1,a2,val+1); a1=a2=0; } } } return sum*2; } int main(){ io_opt; cin>>s; int dep=0; for(int i=0;i<s.size();i++){ if(s[i]=='('){ dep++; a[i]=dep; } else{ a[i]=dep; dep--; } }
int ans=0,x1=-1,x2=-1; for(int i=0;i<=s.size();i++){ if(a[i]==1){ if(x1==-1){ x1=i; } else{ x2=i; ans+=dfs(x1,x2,1);
x1=x2=-1; } } } cout<<ans<<endl; return 0; }
|