Overview
| SHA1 Hash: | 7f9fcaa19ccd33367fc481c10a1fb71c4d04edbc |
|---|---|
| Date: | 2013-08-02 01:01:11 |
| User: | kinaba |
| Comment: | Done. |
| 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/586-U/1A.cpp version [52a3481b42a5f211]
> 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+=y; } > 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 > 36 class TrafficCongestion { public: > 37 int theMinCars(int treeHeight) > 38 { > 39 vector<mint> dp(treeHeight+1); > 40 vector<mint> sum(treeHeight+1); > 41 dp[0] = 1; > 42 sum[0] = dp[0]; > 43 dp[1] = 1; > 44 sum[1] = dp[1] + sum[0]; > 45 for(int h=2; h<=treeHeight; ++h) > 46 { > 47 dp[h] = sum[h-2]*2 + 1; > 48 sum[h] = dp[h] + sum[h-1]; > 49 } > 50 return dp[treeHeight].val; > 51 } > 52 }; > 53 > 54 // BEGIN CUT HERE > 55 #include <ctime> > 56 double start_time; string timer() > 57 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 58 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 59 { os << "{ "; > 60 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 61 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 62 void verify_case(const int& Expected, const int& Received) { > 63 bool ok = (Expected == Received); > 64 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 65 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 66 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 67 #define END verify_case(_, TrafficCongestion().theMinCars(treeHeight));} > 68 int main(){ > 69 > 70 CASE(0) > 71 int treeHeight = 1; > 72 int _ = 1; > 73 END > 74 CASE(1) > 75 int treeHeight = 2; > 76 int _ = 3; > 77 END > 78 CASE(2) > 79 int treeHeight = 3; > 80 int _ = 5; > 81 END > 82 CASE(3) > 83 int treeHeight = 585858; > 84 int _ = 548973404; > 85 END > 86 CASE(4) > 87 int treeHeight = 5; > 88 int _ = -1; > 89 END > 90 /* > 91 CASE(5) > 92 int treeHeight = ; > 93 int _ = ; > 94 END > 95 */ > 96 } > 97 // END CUT HERE
Added SRM/586-U/1B-U.cpp version [2d35ffe80728cb4c]
> 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 LISNumber { public: > 50 int count(vector <int> cardsnum, int K) > 51 { > 52 memo.assign(accumulate(cardsnum.begin(), cardsnum.end(), 1)*card > 53 return rec(1, 0, cardsnum, 0, K); > 54 } > 55 > 56 vector<int> memo; > 57 int rec(int blks, int may, const vector<int>& cards, int i, int K) > 58 { > 59 if(i == cards.size()) > 60 return (K == may); > 61 if(K<may) > 62 return 0; > 63 > 64 int key = may*cards.size() + i; > 65 if(memo[key] != -1) > 66 return memo[key]; > 67 > 68 int c = cards[i]; > 69 > 70 mint total = 0; > 71 for(int use=1; use<=blks && use<=c; ++use) > 72 { > 73 for(int use_may=0; use_may<=use; ++use_may) > 74 if(use-use_may<=blks-may && use_may<=may) > 75 total += C(blks-may, use-use_may) * C(may, use_m > 76 } > 77 return memo[key] = total.val; > 78 } > 79 }; > 80 > 81 // BEGIN CUT HERE > 82 #include <ctime> > 83 double start_time; string timer() > 84 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 85 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 86 { os << "{ "; > 87 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 88 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 89 void verify_case(const int& Expected, const int& Received) { > 90 bool ok = (Expected == Received); > 91 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 92 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 93 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 94 #define END verify_case(_, LISNumber().count(cardsnum, K));} > 95 int main(){ > 96 /* > 97 CASE(0) > 98 int cardsnum_[] = {1, 1, 1}; > 99 vector <int> cardsnum(cardsnum_, cardsnum_+sizeof(cardsnum_)/sizeof(*c > 100 int K = 2; > 101 int _ = 4; > 102 END > 103 */ > 104 CASE(1) > 105 int cardsnum_[] = {2}; > 106 vector <int> cardsnum(cardsnum_, cardsnum_+sizeof(cardsnum_)/sizeof(*c > 107 int K = 1; > 108 int _ = 0; > 109 END > 110 CASE(2) > 111 int cardsnum_[] = {36, 36, 36, 36, 36}; > 112 vector <int> cardsnum(cardsnum_, cardsnum_+sizeof(cardsnum_)/sizeof(*c > 113 int K = 36; > 114 int _ = 1; > 115 END > 116 CASE(3) > 117 int cardsnum_[] = {3, 2, 11, 5, 7}; > 118 vector <int> cardsnum(cardsnum_, cardsnum_+sizeof(cardsnum_)/sizeof(*c > 119 int K = 20; > 120 int _ = 474640725; > 121 END > 122 CASE(4) > 123 int cardsnum_[] = {31, 4, 15, 9, 26, 5, 35, 8, 9, 7, 9, 32, 3, 8, 4, 6, > 124 vector <int> cardsnum(cardsnum_, cardsnum_+sizeof(cardsnum_)/sizeof(*c > 125 int K = 58; > 126 int _ = 12133719; > 127 END > 128 CASE(5) > 129 int cardsnum_[] = {27, 18, 28, 18, 28, 4, 5, 9, 4, 5, 23, 5, > 130 36, 28, 7, 4, 7, 13, 5, 26, 6, 24, 9, 7, > 131 7, 5, 7, 24, 7, 9, 36, 9, 9, 9, 5, 9}; > 132 vector <int> cardsnum(cardsnum_, cardsnum_+sizeof(cardsnum_)/sizeof(*c > 133 int K = 116; > 134 int _ = 516440918; > 135 END > 136 CASE(6) > 137 int cardsnum_[] = { > 138 36,36,36,36,36,36, > 139 36,36,36,36,36,36, > 140 36,36,36,36,36,36, > 141 36,36,36,36,36,36, > 142 36,36,36,36,36,36, > 143 36,36,36,36,36,36}; > 144 vector <int> cardsnum(cardsnum_, cardsnum_+sizeof(cardsnum_)/sizeof(*c > 145 int K = 36*36; > 146 int _ = -1; > 147 END > 148 /* > 149 CASE(7) > 150 int cardsnum_[] = ; > 151 vector <int> cardsnum(cardsnum_, cardsnum_+sizeof(cardsnum_)/sizeof(*c > 152 int K = ; > 153 int _ = ; > 154 END > 155 */ > 156 } > 157 // END CUT HERE
Modified lib/numeric/modArith.cpp from [065fcd1fef379fbc] to [c76c99fca94dfde1].
32 mint FAC(LL n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*FAC_.size() 32 mint FAC(LL n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*FAC_.size() 33 33 34 // nCk :: O(log MODVAL) time, O(n) space. 34 // nCk :: O(log MODVAL) time, O(n) space. 35 mint C(LL n, LL k) { return k<0 || n<k ? 0 : FAC(n) / (FAC(k) * FAC(n-k)); } 35 mint C(LL n, LL k) { return k<0 || n<k ? 0 : FAC(n) / (FAC(k) * FAC(n-k)); } 36 36 37 // nCk :: O(1) time, O(n^2) space. 37 // nCk :: O(1) time, O(n^2) space. 38 vector< vector<mint> > CP_; 38 vector< vector<mint> > CP_; 39 mint C(LL n, LL k) { | 39 mint C(int n, int k) { 40 while( CP_.size() <= n ) { 40 while( CP_.size() <= n ) { 41 int nn = CP_.size(); 41 int nn = CP_.size(); 42 CP_.push_back(vector<mint>(nn+1,1)); 42 CP_.push_back(vector<mint>(nn+1,1)); 43 for(int kk=1; kk<nn; ++kk) 43 for(int kk=1; kk<nn; ++kk) 44 CP_[nn][kk] = CP_[nn-1][kk-1] + CP_[nn-1][kk]; 44 CP_[nn][kk] = CP_[nn-1][kk-1] + CP_[nn-1][kk]; 45 } 45 } 46 return k<0 || n<k ? 0 : CP_[n][k]; 46 return k<0 || n<k ? 0 : CP_[n][k];