e87d5512af 2011-06-03 kinaba: #include <iostream> e87d5512af 2011-06-03 kinaba: #include <sstream> e87d5512af 2011-06-03 kinaba: #include <iomanip> e87d5512af 2011-06-03 kinaba: #include <vector> e87d5512af 2011-06-03 kinaba: #include <string> e87d5512af 2011-06-03 kinaba: #include <map> e87d5512af 2011-06-03 kinaba: #include <set> e87d5512af 2011-06-03 kinaba: #include <algorithm> e87d5512af 2011-06-03 kinaba: #include <numeric> e87d5512af 2011-06-03 kinaba: #include <iterator> e87d5512af 2011-06-03 kinaba: #include <functional> e87d5512af 2011-06-03 kinaba: #include <complex> e87d5512af 2011-06-03 kinaba: #include <queue> e87d5512af 2011-06-03 kinaba: #include <stack> e87d5512af 2011-06-03 kinaba: #include <cmath> e87d5512af 2011-06-03 kinaba: #include <cassert> e87d5512af 2011-06-03 kinaba: #include <cstring> e87d5512af 2011-06-03 kinaba: using namespace std; e87d5512af 2011-06-03 kinaba: typedef long long LL; e87d5512af 2011-06-03 kinaba: typedef complex<double> CMP; e87d5512af 2011-06-03 kinaba: e87d5512af 2011-06-03 kinaba: class YetAnotherORProblem { public: e87d5512af 2011-06-03 kinaba: map<vector<LL>, int> memo; e87d5512af 2011-06-03 kinaba: int countSequences(const vector<LL>& R) e87d5512af 2011-06-03 kinaba: { e87d5512af 2011-06-03 kinaba: if( count(R.begin(),R.end(),0) == R.size() ) e87d5512af 2011-06-03 kinaba: return 1; e87d5512af 2011-06-03 kinaba: if( memo.count(R) ) e87d5512af 2011-06-03 kinaba: return memo[R]; e87d5512af 2011-06-03 kinaba: e87d5512af 2011-06-03 kinaba: vector<LL> RR; e87d5512af 2011-06-03 kinaba: for(int i=0; i<R.size(); ++i) e87d5512af 2011-06-03 kinaba: RR.push_back(R[i]/2); e87d5512af 2011-06-03 kinaba: e87d5512af 2011-06-03 kinaba: int total = countSequences(RR); e87d5512af 2011-06-03 kinaba: for(int i=0; i<R.size(); ++i) e87d5512af 2011-06-03 kinaba: if( R[i] ) e87d5512af 2011-06-03 kinaba: { e87d5512af 2011-06-03 kinaba: if( (R[i]&1) == 0 ) RR[i]--; e87d5512af 2011-06-03 kinaba: total = (total + countSequences(RR)) % 1000000009; e87d5512af 2011-06-03 kinaba: if( (R[i]&1) == 0 ) RR[i]++; e87d5512af 2011-06-03 kinaba: } e87d5512af 2011-06-03 kinaba: return memo[R] = total; e87d5512af 2011-06-03 kinaba: } e87d5512af 2011-06-03 kinaba: }; e87d5512af 2011-06-03 kinaba: e87d5512af 2011-06-03 kinaba: // BEGIN CUT HERE e87d5512af 2011-06-03 kinaba: #include <ctime> e87d5512af 2011-06-03 kinaba: double start_time; string timer() e87d5512af 2011-06-03 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } e87d5512af 2011-06-03 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) e87d5512af 2011-06-03 kinaba: { os << "{ "; e87d5512af 2011-06-03 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) e87d5512af 2011-06-03 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } e87d5512af 2011-06-03 kinaba: void verify_case(const int& Expected, const int& Received) { e87d5512af 2011-06-03 kinaba: bool ok = (Expected == Received); e87d5512af 2011-06-03 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; e87d5512af 2011-06-03 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } e87d5512af 2011-06-03 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); e87d5512af 2011-06-03 kinaba: #define END verify_case(_, YetAnotherORProblem().countSequences(R));} e87d5512af 2011-06-03 kinaba: int main(){ e87d5512af 2011-06-03 kinaba: e87d5512af 2011-06-03 kinaba: CASE(0) e87d5512af 2011-06-03 kinaba: long R_[] = {3,5}; e87d5512af 2011-06-03 kinaba: vector<long long> R(R_, R_+sizeof(R_)/sizeof(*R_)); e87d5512af 2011-06-03 kinaba: int _ = 15; e87d5512af 2011-06-03 kinaba: END e87d5512af 2011-06-03 kinaba: CASE(1) e87d5512af 2011-06-03 kinaba: long R_[] = {3,3,3}; e87d5512af 2011-06-03 kinaba: vector<long long> R(R_, R_+sizeof(R_)/sizeof(*R_)); e87d5512af 2011-06-03 kinaba: int _ = 16; e87d5512af 2011-06-03 kinaba: END e87d5512af 2011-06-03 kinaba: CASE(2) e87d5512af 2011-06-03 kinaba: long R_[] = {1,128}; e87d5512af 2011-06-03 kinaba: vector<long long> R(R_, R_+sizeof(R_)/sizeof(*R_)); e87d5512af 2011-06-03 kinaba: int _ = 194; e87d5512af 2011-06-03 kinaba: END e87d5512af 2011-06-03 kinaba: CASE(3) e87d5512af 2011-06-03 kinaba: long R_[] = {26,74,25,30}; e87d5512af 2011-06-03 kinaba: vector<long long> R(R_, R_+sizeof(R_)/sizeof(*R_)); e87d5512af 2011-06-03 kinaba: int _ = 8409; e87d5512af 2011-06-03 kinaba: END e87d5512af 2011-06-03 kinaba: CASE(4) e87d5512af 2011-06-03 kinaba: long R_[] = {1000000000,1000000000}; e87d5512af 2011-06-03 kinaba: vector<long long> R(R_, R_+sizeof(R_)/sizeof(*R_)); e87d5512af 2011-06-03 kinaba: int _ = 420352509; e87d5512af 2011-06-03 kinaba: END e87d5512af 2011-06-03 kinaba: CASE(5) e87d5512af 2011-06-03 kinaba: long long R_[] = {1000000000000000000LL,1000000000000000000LL,1000000000000000000LL,1000000000000000000LL,1000000000000000000LL,1000000000000000000LL,1000000000000000000LL,1000000000000000000LL,1000000000000000000LL,1000000000000000000LL}; e87d5512af 2011-06-03 kinaba: vector<long long> R(R_, R_+sizeof(R_)/sizeof(*R_)); e87d5512af 2011-06-03 kinaba: int _ = -1; e87d5512af 2011-06-03 kinaba: END e87d5512af 2011-06-03 kinaba: CASE(6) e87d5512af 2011-06-03 kinaba: long long R_[] = {1, 1}; e87d5512af 2011-06-03 kinaba: vector<long long> R(R_, R_+sizeof(R_)/sizeof(*R_)); e87d5512af 2011-06-03 kinaba: int _ = 3; e87d5512af 2011-06-03 kinaba: END e87d5512af 2011-06-03 kinaba: CASE(6) e87d5512af 2011-06-03 kinaba: long long R_[] = {0xfffffffffffffffLL, 0xfffffffffffffffLL, 0xfffffffffffffffLL, 0xfffffffffffffffLL, 0xfffffffffffffffLL, 0xfffffffffffffffLL, 0xfffffffffffffffLL, 0xfffffffffffffffLL, 0xfffffffffffffffLL, 0xfffffffffffffffLL, }; e87d5512af 2011-06-03 kinaba: vector<long long> R(R_, R_+sizeof(R_)/sizeof(*R_)); e87d5512af 2011-06-03 kinaba: int _ = 3; e87d5512af 2011-06-03 kinaba: END e87d5512af 2011-06-03 kinaba: e87d5512af 2011-06-03 kinaba: } e87d5512af 2011-06-03 kinaba: // END CUT HERE