Overview
| SHA1 Hash: | 6828085ccd61d1983837ae3c860cc7ed194eae80 |
|---|---|
| Date: | 2015-09-11 13:38:27 |
| User: | kinaba |
| Comment: | 666 |
| 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/666-U/1A-U.cpp version [5237c6bbcc22042e]
> 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 WalkOverATree { public: > 23 int maxNodesVisited(vector <int> parent, int L) > 24 { > 25 const int N = parent.size() + 1; > 26 vector<vector<int>> G(N); > 27 for(int i=0; i<parent.size(); ++i) > 28 G[parent[i]].push_back(i+1); > 29 > 30 vector<int> numBelow(N); { > 31 function<int(int)> rec; > 32 rec = [&](int v) { > 33 int cnt = 1; > 34 for(auto u: G[v]) > 35 cnt += rec(u); > 36 return numBelow[v] = cnt; > 37 }; > 38 rec(0); > 39 } > 40 > 41 function<int(int, int)> rec; > 42 map<pair<int,int>, int> memo; > 43 rec = [&](int v, int L) { > 44 const pair<int,int> key(v, L); > 45 if(memo.count(key)) return memo[key]; > 46 > 47 const vector<int>& child = G[v]; > 48 if(L<=0 || child.empty()) > 49 return 1; > 50 > 51 int visMax = 0; > 52 for(int i=0; i<child.size(); ++i) { > 53 set<int> previsit; > 54 previsit.insert(0); > 55 for(int k=0; k<child.size(); ++k) if(i!=k) { > 56 set<int> pv2 = previsit; > 57 for(int z: previsit) > 58 pv2.insert(z + numBelow[child[k] > 59 previsit = pv2; > 60 } > 61 > 62 for(int p: previsit) if(p*2 <= L) > 63 visMax = max(visMax, 1 + p + rec(child[i > 64 } > 65 return memo[key] = visMax; > 66 }; > 67 return rec(0, L); > 68 } > 69 }; > 70 > 71 // BEGIN CUT HERE > 72 #include <ctime> > 73 double start_time; string timer() > 74 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 75 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 76 { os << "{ "; > 77 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 78 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 79 void verify_case(const int& Expected, const int& Received) { > 80 bool ok = (Expected == Received); > 81 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 82 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 83 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 84 #define END verify_case(_, WalkOverATree().maxNodesVisited(parent, L));} > 85 int main(){ > 86 /* > 87 CASE(0) > 88 int parent_[] = {0, 0}; > 89 vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_)) > 90 int L = 2; > 91 int _ = 2; > 92 END > 93 */ > 94 CASE(1) > 95 int parent_[] = {0, 0}; > 96 vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_)) > 97 int L = 3; > 98 int _ = 3; > 99 END > 100 CASE(2) > 101 int parent_[] = {0, 1, 2, 3}; > 102 vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_)) > 103 int L = 2; > 104 int _ = 3; > 105 END > 106 CASE(3) > 107 int parent_[] = {0,0,0,0,2,4,2,3,1}; > 108 vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_)) > 109 int L = 1; > 110 int _ = 2; > 111 END > 112 CASE(4) > 113 int parent_[] = {0,0,1,2,3,2,3,1,3,0,1,8,6,8,0,5,15,0,9}; > 114 vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_)) > 115 int L = 4; > 116 int _ = 5; > 117 END > 118 CASE(5) > 119 int parent_[] = {0,0,0,1,1,3,5,1,4,5,2,2,10,5,10,10,11,13,8,3,18,15,20,2 > 120 vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_)) > 121 int L = 26; > 122 int _ = 17; > 123 END > 124 CASE(6) > 125 int parent_[] = {0, 0, 2, 0} > 126 ; > 127 vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_)) > 128 int L = 100; > 129 int _ = 5; > 130 END > 131 CASE(7) > 132 int parent_[] = {0, 0, 2}; > 133 vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_)) > 134 int L = 4; > 135 int _ = 4; > 136 END > 137 CASE(8) > 138 int parent_[] = {0,1,2,0,4,4,4,4}; > 139 vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_)) > 140 int L = 3; > 141 int _ = 4; > 142 END > 143 CASE(9) > 144 int parent_[] = {0,0,2,0,4,5}; > 145 vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_)) > 146 int L = 7; > 147 int _ = 6; > 148 END > 149 } > 150 // END CUT HERE
Added SRM/666-U/1B.cpp version [527ef29abc31b652]
> 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 > 38 vector< vector<mint> > CP_; > 39 mint C(int n, int k) { > 40 while( CP_.size() <= n ) { > 41 int nn = CP_.size(); > 42 CP_.push_back(vector<mint>(nn+1,1)); > 43 for(int kk=1; kk<nn; ++kk) > 44 CP_[nn][kk] = CP_[nn-1][kk-1] + CP_[nn-1][kk]; > 45 } > 46 return k<0 || n<k ? 0 : CP_[n][k]; > 47 } > 48 > 49 class SumOverPermutations { public: > 50 int N; > 51 vector<int> memoOO, memoCO, memoCC; > 52 > 53 int findSum(int n) > 54 { > 55 N = n; > 56 memoOO.assign(N+1, -1); > 57 memoCO.assign(N+1, -1); > 58 memoCC.assign(N+1, -1); > 59 return recOO(n); > 60 } > 61 > 62 int recOO(int k) { > 63 if(k == 0) return 1; > 64 if(k == 1) return N; > 65 if(memoOO[k] != -1) return memoOO[k]; > 66 > 67 mint total = 0; > 68 total += mint(N) * recCO(k-1); // left > 69 total += mint(N) * recCO(k-1); // right > 70 for(int i=1; i+1<k; ++i) // mid > 71 total += mint(N) * recCO(i) * recCO(k-1-i) * C(k-1, i); > 72 return memoOO[k] = total.val; > 73 } > 74 > 75 int recCO(int k) { > 76 if(k == 0) return 1; > 77 if(k == 1) return N-1; > 78 if(memoCO[k] != -1) return memoCO[k]; > 79 > 80 mint total = 0; > 81 total += mint(N-1) * recCO(k-1); // left > 82 total += mint(N) * recCC(k-1); // right > 83 for(int i=1; i+1<k; ++i) // mid > 84 total += mint(N) * recCC(i) * recCO(k-1-i) * C(k-1, i); > 85 return memoCO[k] = total.val; > 86 } > 87 > 88 mint recCC(int k) { > 89 if(k == 0) return 1; > 90 if(k == 1) return N-2; > 91 if(memoCC[k] != -1) return memoCC[k]; > 92 > 93 mint total = 0; > 94 total += mint(N-1) * recCC(k-1); // left > 95 total += mint(N-1) * recCC(k-1); // right > 96 for(int i=1; i+1<k; ++i) // mid > 97 total += mint(N) * recCC(i) * recCC(k-1-i) * C(k-1, i); > 98 return memoCC[k] = total.val; > 99 } > 100 }; > 101 > 102 // BEGIN CUT HERE > 103 #include <ctime> > 104 double start_time; string timer() > 105 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 106 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 107 { os << "{ "; > 108 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 109 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 110 void verify_case(const int& Expected, const int& Received) { > 111 bool ok = (Expected == Received); > 112 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 113 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 114 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 115 #define END verify_case(_, SumOverPermutations().findSum(n));} > 116 int main(){ > 117 > 118 CASE(0) > 119 int n = 2; > 120 int _ = 4; > 121 END > 122 CASE(1) > 123 int n = 3; > 124 int _ = 66; > 125 END > 126 CASE(2) > 127 int n = 10; > 128 int _ = 58310114; > 129 END > 130 CASE(3) > 131 int n = 3900; > 132 int _ = 940560814; > 133 END > 134 /* > 135 CASE(4) > 136 int n = ; > 137 int _ = ; > 138 END > 139 CASE(5) > 140 int n = ; > 141 int _ = ; > 142 END > 143 */ > 144 } > 145 // END CUT HERE
Added SRM/666-U/1C-U.cpp version [6384de8b9346d7d3]
> 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 > 38 class CountBinarySequences { public: > 39 int countSequences(int n, int k, vector <int> L, vector <int> R) > 40 { > 41 const int N = L.size(); > 42 vector<pair<int,int>> RNG; > 43 for(int i=0; i<N; ++i) > 44 RNG.emplace_back(L[i], R[i]); > 45 sort(RNG.begin(), RNG.end(), [&](pair<int,int> a, pair<int,int> > 46 if(a.second-a.first != b.second-b.first) > 47 return a.second-a.first < b.second-b.first; > 48 return a<b; > 49 }); > 50 > 51 vector<vector<int>> child(N+1); > 52 for(int i=0; i<N; ++i) { > 53 int p = N; > 54 for(int k=i+1; k<N; ++k) > 55 if(RNG[k].first<=RNG[i].first && RNG[i].second<= > 56 {p=k; break;} > 57 child[p].emplace_back(i); > 58 } > 59 for(auto& cc: child) > 60 sort(cc.begin(), cc.end(), [&](int a, int b){ > 61 return RNG[a].first < RNG[b].first; > 62 }); > 63 > 64 RNG.emplace_back(1, n); > 65 > 66 memo.assign((N+1)*(k+1)*(k+1), -1); > 67 > 68 mint total = 0; > 69 for(int l=0; l<=k; ++l) > 70 for(int r=0; r<=k; ++r) > 71 total += solve(RNG, child, k, N, l, r); > 72 return total.val; > 73 } > 74 > 75 vector<int> memo; > 76 int solve( > 77 const vector<pair<int,int>>& RNG, > 78 const vector<vector<int>>& rng_list, > 79 const int K, > 80 int idx, int L1, int R1) { > 81 const bool must_be_even = (idx+1 == RNG.size()); > 82 const int key = (idx*(K+1)+L1)*(K+1)+R1; > 83 if(memo[key] != -1) return memo[key]; > 84 > 85 // RNG[idx] is the current range you need to consider. > 86 // rng_list[idx] is left-to-right sorted sub-ranges. > 87 // the region must be sum-even if must_be_even. > 88 // more than K consecutive 1's are not allowed. > 89 // left-end must have exactly L1 consecutive 1's. > 90 // right-end must have exactly R1 consecutive 1's. > 91 return memo[key] = 0; > 92 } > 93 }; > 94 > 95 // BEGIN CUT HERE > 96 #include <ctime> > 97 double start_time; string timer() > 98 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 99 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 100 { os << "{ "; > 101 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 102 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 103 void verify_case(const int& Expected, const int& Received) { > 104 bool ok = (Expected == Received); > 105 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 106 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 107 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 108 #define END verify_case(_, CountBinarySequences().countSequences(n, k, L, R > 109 int main(){ > 110 > 111 CASE(0) > 112 int n = 4; > 113 int k = 2; > 114 int L_[] = {2}; > 115 vector <int> L(L_, L_+sizeof(L_)/sizeof(*L_)); > 116 int R_[] = {3}; > 117 vector <int> R(R_, R_+sizeof(R_)/sizeof(*R_)); > 118 int _ = 5; > 119 END > 120 CASE(1) > 121 int n = 4; > 122 int k = 1; > 123 int L_[] = {2}; > 124 vector <int> L(L_, L_+sizeof(L_)/sizeof(*L_)); > 125 int R_[] = {2}; > 126 vector <int> R(R_, R_+sizeof(R_)/sizeof(*R_)); > 127 int _ = 6; > 128 END > 129 CASE(2) > 130 int n = 6; > 131 int k = 3; > 132 int L_[] = {1, 2, 3}; > 133 vector <int> L(L_, L_+sizeof(L_)/sizeof(*L_)); > 134 int R_[] = {6, 5, 4}; > 135 vector <int> R(R_, R_+sizeof(R_)/sizeof(*R_)); > 136 int _ = 6; > 137 END > 138 CASE(3) > 139 int n = 1000; > 140 int k = 4; > 141 int L_[] = {10, 101, 201, 110, 121}; > 142 vector <int> L(L_, L_+sizeof(L_)/sizeof(*L_)); > 143 int R_[] = {100, 200, 300, 120, 130}; > 144 vector <int> R(R_, R_+sizeof(R_)/sizeof(*R_)); > 145 int _ = 444743885; > 146 END > 147 CASE(4) > 148 int n = 1; > 149 int k = 5; > 150 int L_[] = {1}; > 151 vector <int> L(L_, L_+sizeof(L_)/sizeof(*L_)); > 152 int R_[] = {1}; > 153 vector <int> R(R_, R_+sizeof(R_)/sizeof(*R_)); > 154 int _ = 1; > 155 END > 156 CASE(5) > 157 int n = 998; > 158 int k = 2; > 159 int L_[] = {313,365,189,913,334,360,160,931,313,402,389,328,376,47,906,3 > 160 vector <int> L(L_, L_+sizeof(L_)/sizeof(*L_)); > 161 int R_[] = {313,365,189,913,334,362,160,931,340,405,389,329,398,425,907, > 162 vector <int> R(R_, R_+sizeof(R_)/sizeof(*R_)); > 163 int _ = 420889003; > 164 END > 165 /* > 166 CASE(6) > 167 int n = ; > 168 int k = ; > 169 int L_[] = ; > 170 vector <int> L(L_, L_+sizeof(L_)/sizeof(*L_)); > 171 int R_[] = ; > 172 vector <int> R(R_, R_+sizeof(R_)/sizeof(*R_)); > 173 int _ = ; > 174 END > 175 CASE(7) > 176 int n = ; > 177 int k = ; > 178 int L_[] = ; > 179 vector <int> L(L_, L_+sizeof(L_)/sizeof(*L_)); > 180 int R_[] = ; > 181 vector <int> R(R_, R_+sizeof(R_)/sizeof(*R_)); > 182 int _ = ; > 183 END > 184 */ > 185 } > 186 // END CUT HERE