a57e4e95ff 2016-04-15 kinaba: #include <iostream> a57e4e95ff 2016-04-15 kinaba: #include <sstream> a57e4e95ff 2016-04-15 kinaba: #include <iomanip> a57e4e95ff 2016-04-15 kinaba: #include <vector> a57e4e95ff 2016-04-15 kinaba: #include <string> a57e4e95ff 2016-04-15 kinaba: #include <map> a57e4e95ff 2016-04-15 kinaba: #include <set> a57e4e95ff 2016-04-15 kinaba: #include <algorithm> a57e4e95ff 2016-04-15 kinaba: #include <numeric> a57e4e95ff 2016-04-15 kinaba: #include <iterator> a57e4e95ff 2016-04-15 kinaba: #include <functional> a57e4e95ff 2016-04-15 kinaba: #include <complex> a57e4e95ff 2016-04-15 kinaba: #include <queue> a57e4e95ff 2016-04-15 kinaba: #include <stack> a57e4e95ff 2016-04-15 kinaba: #include <cmath> a57e4e95ff 2016-04-15 kinaba: #include <cassert> a57e4e95ff 2016-04-15 kinaba: #include <tuple> a57e4e95ff 2016-04-15 kinaba: using namespace std; a57e4e95ff 2016-04-15 kinaba: typedef long long LL; a57e4e95ff 2016-04-15 kinaba: typedef complex<double> CMP; a57e4e95ff 2016-04-15 kinaba: a57e4e95ff 2016-04-15 kinaba: class BracketSequenceDiv1 { public: a57e4e95ff 2016-04-15 kinaba: long long count(string s) a57e4e95ff 2016-04-15 kinaba: { a57e4e95ff 2016-04-15 kinaba: return count_multi(s, 0, s.size()) - 1; a57e4e95ff 2016-04-15 kinaba: } a57e4e95ff 2016-04-15 kinaba: a57e4e95ff 2016-04-15 kinaba: map<pair<int,int>, LL> memo1; a57e4e95ff 2016-04-15 kinaba: LL count_multi(const string& str, int s, int e) { a57e4e95ff 2016-04-15 kinaba: if(s == e) a57e4e95ff 2016-04-15 kinaba: return 1; a57e4e95ff 2016-04-15 kinaba: pair<int,int> key(s,e); a57e4e95ff 2016-04-15 kinaba: if(memo1.count(key)) a57e4e95ff 2016-04-15 kinaba: return memo1[key]; a57e4e95ff 2016-04-15 kinaba: a57e4e95ff 2016-04-15 kinaba: LL total = 1; a57e4e95ff 2016-04-15 kinaba: for(int m=s+2; m<=e; ++m) a57e4e95ff 2016-04-15 kinaba: total += count_oneblock(str, s, m) * count_multi(str, m, e); a57e4e95ff 2016-04-15 kinaba: return memo1[key] = total; a57e4e95ff 2016-04-15 kinaba: } a57e4e95ff 2016-04-15 kinaba: a57e4e95ff 2016-04-15 kinaba: map<pair<int,int>, LL> memo2; a57e4e95ff 2016-04-15 kinaba: LL count_oneblock(const string& str, int s, int e) { a57e4e95ff 2016-04-15 kinaba: if(s == e) a57e4e95ff 2016-04-15 kinaba: return 0; a57e4e95ff 2016-04-15 kinaba: if(str[e-1]=='(' || str[e-1]=='[') a57e4e95ff 2016-04-15 kinaba: return 0; a57e4e95ff 2016-04-15 kinaba: const char op = (str[e-1]==')' ? '(' : '['); a57e4e95ff 2016-04-15 kinaba: a57e4e95ff 2016-04-15 kinaba: pair<int,int> key(s,e); a57e4e95ff 2016-04-15 kinaba: if(memo2.count(key)) a57e4e95ff 2016-04-15 kinaba: return memo2[key]; a57e4e95ff 2016-04-15 kinaba: a57e4e95ff 2016-04-15 kinaba: LL total = 0; a57e4e95ff 2016-04-15 kinaba: for(int k=s; k<e; ++k) a57e4e95ff 2016-04-15 kinaba: if(str[k] == op) a57e4e95ff 2016-04-15 kinaba: total += count_multi(str, k+1, e-1); a57e4e95ff 2016-04-15 kinaba: return memo2[key] = total; a57e4e95ff 2016-04-15 kinaba: } a57e4e95ff 2016-04-15 kinaba: }; a57e4e95ff 2016-04-15 kinaba: a57e4e95ff 2016-04-15 kinaba: // BEGIN CUT HERE a57e4e95ff 2016-04-15 kinaba: #include <ctime> a57e4e95ff 2016-04-15 kinaba: double start_time; string timer() a57e4e95ff 2016-04-15 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } a57e4e95ff 2016-04-15 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) a57e4e95ff 2016-04-15 kinaba: { os << "{ "; a57e4e95ff 2016-04-15 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) a57e4e95ff 2016-04-15 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } a57e4e95ff 2016-04-15 kinaba: void verify_case(const long long& Expected, const long long& Received) { a57e4e95ff 2016-04-15 kinaba: bool ok = (Expected == Received); a57e4e95ff 2016-04-15 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; a57e4e95ff 2016-04-15 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } a57e4e95ff 2016-04-15 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); a57e4e95ff 2016-04-15 kinaba: #define END verify_case(_, BracketSequenceDiv1().count(s));} a57e4e95ff 2016-04-15 kinaba: int main(){ a57e4e95ff 2016-04-15 kinaba: a57e4e95ff 2016-04-15 kinaba: CASE(0) a57e4e95ff 2016-04-15 kinaba: string s = "()[]"; a57e4e95ff 2016-04-15 kinaba: long long _ = 3LL; a57e4e95ff 2016-04-15 kinaba: END a57e4e95ff 2016-04-15 kinaba: CASE(1) a57e4e95ff 2016-04-15 kinaba: string s = "())"; a57e4e95ff 2016-04-15 kinaba: long long _ = 2LL; a57e4e95ff 2016-04-15 kinaba: END a57e4e95ff 2016-04-15 kinaba: CASE(2) a57e4e95ff 2016-04-15 kinaba: string s = "()()"; a57e4e95ff 2016-04-15 kinaba: long long _ = 4LL; a57e4e95ff 2016-04-15 kinaba: END a57e4e95ff 2016-04-15 kinaba: CASE(3) a57e4e95ff 2016-04-15 kinaba: string s = "([)]"; a57e4e95ff 2016-04-15 kinaba: long long _ = 2LL; a57e4e95ff 2016-04-15 kinaba: END a57e4e95ff 2016-04-15 kinaba: CASE(4) a57e4e95ff 2016-04-15 kinaba: string s = "())[]][]([]()]]()]]]"; a57e4e95ff 2016-04-15 kinaba: long long _ = 3854LL; a57e4e95ff 2016-04-15 kinaba: END a57e4e95ff 2016-04-15 kinaba: /* a57e4e95ff 2016-04-15 kinaba: CASE(5) a57e4e95ff 2016-04-15 kinaba: string s = ; a57e4e95ff 2016-04-15 kinaba: long long _ = LL; a57e4e95ff 2016-04-15 kinaba: END a57e4e95ff 2016-04-15 kinaba: CASE(6) a57e4e95ff 2016-04-15 kinaba: string s = ; a57e4e95ff 2016-04-15 kinaba: long long _ = LL; a57e4e95ff 2016-04-15 kinaba: END a57e4e95ff 2016-04-15 kinaba: */ a57e4e95ff 2016-04-15 kinaba: } a57e4e95ff 2016-04-15 kinaba: // END CUT HERE