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], L-p*2-1)); 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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 82 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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,20,23,8,11,26,4}; 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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 113 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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> b){ 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<=RNG[k].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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 106 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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,383,381,927,338,178,934,933,162,332,191,188,380,912,970,360,161,179,966,405,971,381}; 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,383,382,927,338,178,934,933,162,332,191,188,384,912,970,365,161,179,966,405,971,381}; 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