codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#define hell 1003 int dp[1000][1000][2]; int helper(string &s,int i,int j,int w) { if(i>j) return false; if(i==j) { return s[i]=='T'?w:1-w; } if(dp[i][j][w]!=-1) return dp[i][j][w]; if((j-i+1)==3) { if(s[i]==s[j]) { if(s[i]=='F'||s[i+1]=='^') return 1-w; else return w; } else { if(s[i+1]=='^'||s[i+1]=='|') return w; return 1-w; } } long long int ans=0; for(int k=i+1;k<j;k+=2) { int lt=helper(s,i,k-1,1); // cout<<i<<" "<<k-1<<" "<<lt<<" "<<"true"<<"\n"; int rt=helper(s,k+1,j,1); // cout<<k+1<<" "<<j<<" "<<rt<<" "<<"true"<<"\n"; int lf=helper(s,i,k-1,0); //cout<<i<<" "<<k-1<<" "<<lf<<" "<<"false"<<"\n"; int rf=helper(s,k+1,j,0); //cout<<k+1<<" "<<j<<" "<<rf<<" "<<"false"<<"\n"; if(s[k]=='&') ans+=lt*rt; else if(s[k]=='^') ans+=lt*rf+lf*rt; else ans+=((lt*rt+lf*rt)%hell+lt*rf)%hell; ans%=hell; } return dp[i][j][w]=ans; } int Solution::cnttrue(string A) { memset(dp,-1,sizeof dp); return helper(A,0,A.length()-1,1); }
Private
[
?
]
Run code
Submit