Overview
| SHA1 Hash: | a57e4e95ff4075c916e502fe6aeb3a371697358c |
|---|---|
| Date: | 2016-04-15 14:56:05 |
| User: | kinaba |
| Comment: | 686 |
| Timelines: | family | ancestors | descendants | both | trunk |
| Downloads: | Tarball | ZIP archive |
| Other Links: | files | file ages | manifest |
Tags And Properties
- branch=trunk inherited from [9165bd3629]
- sym-trunk inherited from [9165bd3629]
Changes
Added SRM/686-U/1A.cpp version [ceaca236de3383b6]
> 1 #include <iostream> > 2 #include <sstream> > 3 #include <iomanip> > 4 #include <vector> > 5 #include <string> > 6 #include <map> > 7 #include <set> > 8 #include <algorithm> > 9 #include <numeric> > 10 #include <iterator> > 11 #include <functional> > 12 #include <complex> > 13 #include <queue> > 14 #include <stack> > 15 #include <cmath> > 16 #include <cassert> > 17 #include <tuple> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 class BracketSequenceDiv1 { public: > 23 long long count(string s) > 24 { > 25 return count_multi(s, 0, s.size()) - 1; > 26 } > 27 > 28 map<pair<int,int>, LL> memo1; > 29 LL count_multi(const string& str, int s, int e) { > 30 if(s == e) > 31 return 1; > 32 pair<int,int> key(s,e); > 33 if(memo1.count(key)) > 34 return memo1[key]; > 35 > 36 LL total = 1; > 37 for(int m=s+2; m<=e; ++m) > 38 total += count_oneblock(str, s, m) * count_multi(str, m, > 39 return memo1[key] = total; > 40 } > 41 > 42 map<pair<int,int>, LL> memo2; > 43 LL count_oneblock(const string& str, int s, int e) { > 44 if(s == e) > 45 return 0; > 46 if(str[e-1]=='(' || str[e-1]=='[') > 47 return 0; > 48 const char op = (str[e-1]==')' ? '(' : '['); > 49 > 50 pair<int,int> key(s,e); > 51 if(memo2.count(key)) > 52 return memo2[key]; > 53 > 54 LL total = 0; > 55 for(int k=s; k<e; ++k) > 56 if(str[k] == op) > 57 total += count_multi(str, k+1, e-1); > 58 return memo2[key] = total; > 59 } > 60 }; > 61 > 62 // BEGIN CUT HERE > 63 #include <ctime> > 64 double start_time; string timer() > 65 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 66 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 67 { os << "{ "; > 68 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 69 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 70 void verify_case(const long long& Expected, const long long& Received) { > 71 bool ok = (Expected == Received); > 72 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 73 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 74 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 75 #define END verify_case(_, BracketSequenceDiv1().count(s));} > 76 int main(){ > 77 > 78 CASE(0) > 79 string s = "()[]"; > 80 long long _ = 3LL; > 81 END > 82 CASE(1) > 83 string s = "())"; > 84 long long _ = 2LL; > 85 END > 86 CASE(2) > 87 string s = "()()"; > 88 long long _ = 4LL; > 89 END > 90 CASE(3) > 91 string s = "([)]"; > 92 long long _ = 2LL; > 93 END > 94 CASE(4) > 95 string s = "())[]][]([]()]]()]]]"; > 96 long long _ = 3854LL; > 97 END > 98 /* > 99 CASE(5) > 100 string s = ; > 101 long long _ = LL; > 102 END > 103 CASE(6) > 104 string s = ; > 105 long long _ = LL; > 106 END > 107 */ > 108 } > 109 // END CUT HERE
Added SRM/686-U/1B-U.cpp version [eeebdace328178c2]
> 1 #include <iostream> > 2 #include <sstream> > 3 #include <iomanip> > 4 #include <vector> > 5 #include <string> > 6 #include <map> > 7 #include <set> > 8 #include <algorithm> > 9 #include <numeric> > 10 #include <iterator> > 11 #include <functional> > 12 #include <complex> > 13 #include <queue> > 14 #include <stack> > 15 #include <cmath> > 16 #include <cassert> > 17 #include <tuple> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 static const unsigned MODVAL = 1000000007; > 23 struct mint > 24 { > 25 unsigned val; > 26 mint():val(0){} > 27 mint(int x):val(x%MODVAL) {} > 28 mint(unsigned x):val(x%MODVAL) {} > 29 mint(LL x):val(x%MODVAL) {} > 30 }; > 31 mint& operator+=(mint& x, mint y) { return x = x.val+y.val; } > 32 mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; } > 33 mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; } > 34 mint operator+(mint x, mint y) { return x+=y; } > 35 mint operator-(mint x, mint y) { return x-=y; } > 36 mint operator*(mint x, mint y) { return x*=y; } > 37 mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; } > 38 > 39 class CyclesNumber { public: > 40 vector <int> getExpectation(vector <int> n, vector <int> m) > 41 { > 42 map<int, set<int>> q; > 43 for(int i=0; i<n.size(); ++i) > 44 q[n[i]].insert(m[i]); > 45 > 46 map<pair<int,int>, int> ans; > 47 T(*max_element(n.begin(), n.end()), q, ans); > 48 > 49 vector<int> result; > 50 for(int i=0; i<n.size(); ++i) > 51 result.push_back(ans[make_pair(n[i], m[i])]); > 52 return result; > 53 } > 54 > 55 void T(int n, map<int,set<int>>& q, map<pair<int,int>,int>& ans) > 56 { > 57 vector<mint> Si; > 58 Si.push_back(0); > 59 Si.push_back(1); > 60 for(int i=1; i<=n; ++i) > 61 { > 62 for(int m: q[i]) { > 63 mint total = 0; > 64 for(int f=0; f<Si.size(); ++f) > 65 total += POW(f, m) * Si[f]; > 66 ans[make_pair(i,m)] = total.val; > 67 } > 68 > 69 Si.resize(Si.size()+1); > 70 for(int k=Si.size()-1; k>=1; --k) > 71 Si[k] = Si[k]*i + Si[k-1]; > 72 } > 73 } > 74 }; > 75 > 76 // BEGIN CUT HERE > 77 #include <ctime> > 78 double start_time; string timer() > 79 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 80 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 81 { os << "{ "; > 82 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 83 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 84 void verify_case(const vector <int>& Expected, const vector <int>& Received) { > 85 bool ok = (Expected == Received); > 86 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 87 cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } > 88 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 89 #define END verify_case(_, CyclesNumber().getExpectation(n, m));} > 90 int main(){ > 91 CASE(0) > 92 int n_[] = {2}; > 93 vector <int> n(n_, n_+sizeof(n_)/sizeof(*n_)); > 94 int m_[] = {2}; > 95 vector <int> m(m_, m_+sizeof(m_)/sizeof(*m_)); > 96 int __[] = {5 }; > 97 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 98 END > 99 CASE(1) > 100 int n_[] = {3}; > 101 vector <int> n(n_, n_+sizeof(n_)/sizeof(*n_)); > 102 int m_[] = {0}; > 103 vector <int> m(m_, m_+sizeof(m_)/sizeof(*m_)); > 104 int __[] = {6 }; > 105 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 106 END > 107 CASE(2) > 108 int n_[] = {1, 2, 3}; > 109 vector <int> n(n_, n_+sizeof(n_)/sizeof(*n_)); > 110 int m_[] = {1, 3, 3}; > 111 vector <int> m(m_, m_+sizeof(m_)/sizeof(*m_)); > 112 int __[] = {1, 9, 53 }; > 113 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 114 END > 115 CASE(3) > 116 int n_[] = {10, 20, 30}; > 117 vector <int> n(n_, n_+sizeof(n_)/sizeof(*n_)); > 118 int m_[] = {10, 20, 30}; > 119 vector <int> m(m_, m_+sizeof(m_)/sizeof(*m_)); > 120 int __[] = {586836447, 544389755, 327675273 }; > 121 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 122 END > 123 CASE(4) > 124 int n_[] = {100000}; > 125 vector <int> n(n_, n_+sizeof(n_)/sizeof(*n_)); > 126 int m_[] = {300}; > 127 vector <int> m(m_, m_+sizeof(m_)/sizeof(*m_)); > 128 int __[] = {-1}; > 129 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 130 END > 131 /* > 132 CASE(5) > 133 int n_[] = ; > 134 vector <int> n(n_, n_+sizeof(n_)/sizeof(*n_)); > 135 int m_[] = ; > 136 vector <int> m(m_, m_+sizeof(m_)/sizeof(*m_)); > 137 int __[] = ; > 138 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 139 END > 140 */ > 141 } > 142 // END CUT HERE