Overview
| SHA1 Hash: | 155c399d58f8ec3efb06eff4acba55ba6d38ea8b |
|---|---|
| Date: | 2012-12-08 16:59:00 |
| User: | kinaba |
| Comment: | 562 |
| 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/562-U/1A-U.cpp version [81e3457a1a1154c2]
> 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 using namespace std; > 18 typedef long long LL; > 19 typedef long double LD; > 20 typedef complex<LD> CMP; > 21 > 22 class PastingPaintingDivOne { public: > 23 vector<long long> countColors(vector <string> c, int T) > 24 { > 25 int H = c.size(); > 26 int W = c[0].size(); > 27 > 28 int TR = min(T, 50+T%50); > 29 vector<string> shifted(H+TR+50, string(W+H, '.')); > 30 > 31 // TR > 32 for(int i=0; i<TR; ++i) > 33 for(int y=0; y<H; ++y) > 34 for(int x=0; x<W; ++x) > 35 if(c[y][x] != '.') > 36 shifted[i+y][x+H-1-y] = c[y][x]; > 37 > 38 LL r=0, g=0, b=0; > 39 for(int y=0; y<shifted.size(); ++y) > 40 for(int x=0; x<shifted[y].size(); ++x) > 41 if(shifted[y][x]=='R') r++; > 42 else if(shifted[y][x]=='G') g++; > 43 else if(shifted[y][x]=='B') b++; > 44 > 45 // 50 more > 46 for(int i=TR; i<TR+50; ++i) > 47 for(int y=0; y<H; ++y) > 48 for(int x=0; x<W; ++x) > 49 if(c[y][x] != '.') > 50 shifted[i+y][x+H-1-y] = c[y][x]; > 51 > 52 LL rr=0, gg=0, bb=0; > 53 for(int y=0; y<shifted.size(); ++y) > 54 for(int x=0; x<shifted[y].size(); ++x) > 55 if(shifted[y][x]=='R') rr++; > 56 else if(shifted[y][x]=='G') gg++; > 57 else if(shifted[y][x]=='B') bb++; > 58 > 59 vector<LL> answer; > 60 answer.push_back((rr-r)*(T-TR)/50 + r); > 61 answer.push_back((gg-g)*(T-TR)/50 + g); > 62 answer.push_back((bb-b)*(T-TR)/50 + b); > 63 return answer; > 64 } > 65 }; > 66 > 67 // BEGIN CUT HERE > 68 #include <ctime> > 69 double start_time; string timer() > 70 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 71 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 72 { os << "{ "; > 73 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 74 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 75 void verify_case(const vector<long long>& Expected, const vector<long long>& Rec > 76 bool ok = (Expected == Received); > 77 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 78 cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } > 79 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 80 #define END verify_case(_, PastingPaintingDivOne().countColors(clipboard, T > 81 int main(){ > 82 > 83 CASE(0) > 84 string clipboard_[] = { > 85 "..G", > 86 "R..", > 87 "BG." > 88 }; > 89 vector <string> clipboard(clipboard_, clipboard_+sizeof(clipboard_)/si > 90 int T = 3; > 91 long long __[] = {3, 4, 3 }; > 92 vector<long long> _(__, __+sizeof(__)/sizeof(*__)); > 93 END > 94 CASE(1) > 95 string clipboard_[] = { > 96 "R...", > 97 "....", > 98 "....", > 99 "...R" > 100 }; > 101 vector <string> clipboard(clipboard_, clipboard_+sizeof(clipboard_)/si > 102 int T = 2; > 103 long long __[] = {4, 0, 0 }; > 104 vector<long long> _(__, __+sizeof(__)/sizeof(*__)); > 105 END > 106 CASE(2) > 107 string clipboard_[] = {"RGB"}; > 108 vector <string> clipboard(clipboard_, clipboard_+sizeof(clipboard_)/si > 109 int T = 100000; > 110 long long __[] = {100000, 100000, 100000 }; > 111 vector<long long> _(__, __+sizeof(__)/sizeof(*__)); > 112 END > 113 CASE(3) > 114 string clipboard_[] = {"."}; > 115 vector <string> clipboard(clipboard_, clipboard_+sizeof(clipboard_)/si > 116 int T = 1000000000; > 117 long long __[] = {0, 0, 0 }; > 118 vector<long long> _(__, __+sizeof(__)/sizeof(*__)); > 119 END > 120 CASE(4) > 121 string clipboard_[] = { > 122 "RB.", > 123 ".G." > 124 } > 125 ; > 126 vector <string> clipboard(clipboard_, clipboard_+sizeof(clipboard_)/si > 127 int T = 100; > 128 long long __[] = {100, 1, 100 }; > 129 vector<long long> _(__, __+sizeof(__)/sizeof(*__)); > 130 END > 131 CASE(5) > 132 string clipboard_[] = { > 133 "..........G..........", > 134 ".........G.G.........", > 135 "........G...G........", > 136 ".......G.....G.......", > 137 "......G..B.B..G......", > 138 ".....G...B.B...G.....", > 139 "....G...........G....", > 140 "...G...R.....R...G...", > 141 "..G.....RRRRRR....G..", > 142 ".G..........RR.....G.", > 143 "GGGGGGGGGGGGGGGGGGGGG" > 144 }; > 145 vector <string> clipboard(clipboard_, clipboard_+sizeof(clipboard_)/si > 146 int T = 1000000000; > 147 long long __[] = {2000000018, 17000000048, 2000000005 }; > 148 vector<long long> _(__, __+sizeof(__)/sizeof(*__)); > 149 END > 150 /* > 151 CASE(6) > 152 string clipboard_[] = ; > 153 vector <string> clipboard(clipboard_, clipboard_+sizeof(clipboard_)/si > 154 int T = ; > 155 long long __[] = ; > 156 vector<long long> _(__, __+sizeof(__)/sizeof(*__)); > 157 END > 158 CASE(7) > 159 string clipboard_[] = ; > 160 vector <string> clipboard(clipboard_, clipboard_+sizeof(clipboard_)/si > 161 int T = ; > 162 long long __[] = ; > 163 vector<long long> _(__, __+sizeof(__)/sizeof(*__)); > 164 END > 165 */ > 166 } > 167 // END CUT HERE
Added SRM/562-U/1B-U.cpp version [ce107d8a36905d31]
> 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 using namespace std; > 18 typedef long long LL; > 19 typedef complex<double> CMP; > 20 > 21 class CheckerFreeness { public: > 22 string isFree(vector <string> whiteX, vector <string> whiteY, vector <st > 23 { > 24 stringstream swx(accumulate(whiteX.begin(), whiteX.end(), string > 25 stringstream swy(accumulate(whiteY.begin(), whiteY.end(), string > 26 stringstream sbx(accumulate(blackX.begin(), blackX.end(), string > 27 stringstream sby(accumulate(blackY.begin(), blackY.end(), string > 28 > 29 vector<CMP> w; > 30 for(int x,y; (swx>>x)&&(swy>>y); ) > 31 w.push_back(CMP(x,y)); > 32 > 33 vector<CMP> b; > 34 for(int x,y; (sbx>>x)&&(sby>>y); ) > 35 b.push_back(CMP(x,y)); > 36 > 37 return has_checker(w,b) ? "NO" : "YES"; > 38 } > 39 > 40 bool has_checker(const vector<CMP>& w, const vector<CMP>& b) > 41 { > 42 for(int i=0; i<w.size(); ++i) > 43 for(int k=i+1; k<w.size(); ++k) > 44 if(has_crosser(w[i], w[k], b)) > 45 return true; > 46 return false; > 47 } > 48 > 49 bool has_crosser(CMP a, CMP b, const vector<CMP>& ps) > 50 { > 51 vector<double> arg_a, arg_b; > 52 vector<CMP> qs; > 53 for(int i=0; i<ps.size(); ++i) > 54 { > 55 double d = arg( (ps[i]-a)/(b-a) ); > 56 if(d > 0) { > 57 arg_a.push_back(d); > 58 d = arg( (ps[i]-b)/(b-a) ); > 59 arg_b.push_back(d); > 60 } else { > 61 qs.push_back(ps[i]); > 62 } > 63 } > 64 sort(arg_a.begin(), arg_a.end()); > 65 sort(arg_b.begin(), arg_b.end()); > 66 for(int i=0; i<qs.size(); ++i) > 67 { > 68 CMP q = qs[i]; > 69 double aMax = arg((a-q) / (b-a)); > 70 double bMax = arg((b-q) / (b-a)); > 71 int aNum = lower_bound(arg_a.begin(), arg_a.end(), aMax) > 72 int bNum = lower_bound(arg_b.begin(), arg_b.end(), bMax) > 73 if(aNum != bNum) > 74 return true; > 75 } > 76 return false; > 77 } > 78 }; > 79 > 80 // BEGIN CUT HERE > 81 #include <ctime> > 82 double start_time; string timer() > 83 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 84 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 85 { os << "{ "; > 86 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 87 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 88 void verify_case(const string& Expected, const string& Received) { > 89 bool ok = (Expected == Received); > 90 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 91 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 92 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 93 #define END verify_case(_, CheckerFreeness().isFree(whiteX, whiteY, blackX, > 94 int main(){ > 95 > 96 CASE(0) > 97 string whiteX_[] = {"1 2"}; > 98 vector <string> whiteX(whiteX_, whiteX_+sizeof(whiteX_)/sizeof(*whiteX > 99 string whiteY_[] = {"2 1"}; > 100 vector <string> whiteY(whiteY_, whiteY_+sizeof(whiteY_)/sizeof(*whiteY > 101 string blackX_[] = {"1 2"}; > 102 vector <string> blackX(blackX_, blackX_+sizeof(blackX_)/sizeof(*blackX > 103 string blackY_[] = {"1 2"}; > 104 vector <string> blackY(blackY_, blackY_+sizeof(blackY_)/sizeof(*blackY > 105 string _ = "NO"; > 106 END > 107 CASE(1) > 108 string whiteX_[] = {"2", "5", "3", " ", "1", "7", "3"}; > 109 vector <string> whiteX(whiteX_, whiteX_+sizeof(whiteX_)/sizeof(*whiteX > 110 string whiteY_[] = {"180 254"}; > 111 vector <string> whiteY(whiteY_, whiteY_+sizeof(whiteY_)/sizeof(*whiteY > 112 string blackX_[] = {"32", "5 1", "42"}; > 113 vector <string> blackX(blackX_, blackX_+sizeof(blackX_)/sizeof(*blackX > 114 string blackY_[] = {"462 423"}; > 115 vector <string> blackY(blackY_, blackY_+sizeof(blackY_)/sizeof(*blackY > 116 string _ = "YES"; > 117 END > 118 CASE(2) > 119 string whiteX_[] = {"1 10000000 9999999"}; > 120 vector <string> whiteX(whiteX_, whiteX_+sizeof(whiteX_)/sizeof(*whiteX > 121 string whiteY_[] = {"1 9999999 1"}; > 122 vector <string> whiteY(whiteY_, whiteY_+sizeof(whiteY_)/sizeof(*whiteY > 123 string blackX_[] = {"2 5000000 9999998"}; > 124 vector <string> blackX(blackX_, blackX_+sizeof(blackX_)/sizeof(*blackX > 125 string blackY_[] = {"2 5000001 9999999"}; > 126 vector <string> blackY(blackY_, blackY_+sizeof(blackY_)/sizeof(*blackY > 127 string _ = "YES"; > 128 END > 129 CASE(3) > 130 string whiteX_[] = {"1"}; > 131 vector <string> whiteX(whiteX_, whiteX_+sizeof(whiteX_)/sizeof(*whiteX > 132 string whiteY_[] = {"2"}; > 133 vector <string> whiteY(whiteY_, whiteY_+sizeof(whiteY_)/sizeof(*whiteY > 134 string blackX_[] = {"3"}; > 135 vector <string> blackX(blackX_, blackX_+sizeof(blackX_)/sizeof(*blackX > 136 string blackY_[] = {"4"}; > 137 vector <string> blackY(blackY_, blackY_+sizeof(blackY_)/sizeof(*blackY > 138 string _ = "YES"; > 139 END > 140 CASE(4) > 141 string whiteX_[] = {"6115 9723 3794 2275 2268 2702 3657 915 7953 2743 7" > 142 ,"716 9645 2547 9490 9365 326 6601 5215 6771 7153 72" > 143 ,"93 5922 714 2258 4369 9524 302 8417 6620 1143"}; > 144 vector <string> whiteX(whiteX_, whiteX_+sizeof(whiteX_)/sizeof(*whiteX > 145 string whiteY_[] = {"621 1611 7140 503 5345 7202 681 4908 2510 5908 279" > 146 ,"6 6286 6873 6682 9197 6710 8517 1913 7784 8533 665" > 147 ,"4 446 3561 7241 6168 2025 4739 9501 5340 6446"}; > 148 vector <string> whiteY(whiteY_, whiteY_+sizeof(whiteY_)/sizeof(*whiteY > 149 string blackX_[] = {"6833 131 4151 1776 1959 7210 1903 6107 598 6220 94" > 150 ,"24 5374 6718 2919 6068 6644 5070 710 7121 1630 370" > 151 ,"3 1051 5739 9294 8798 3371 8107 2130 6608 534"}; > 152 vector <string> blackX(blackX_, blackX_+sizeof(blackX_)/sizeof(*blackX > 153 string blackY_[] = {"7496 2412 2801 3473 5810 2714 7853 9714 5470 3558 " > 154 ,"8143 2391 8234 7292 9311 1636 8978 1107 2262 9175 " > 155 ,"7259 8842 5294 7209 2317 3825 3413 820 3774 5393"}; > 156 vector <string> blackY(blackY_, blackY_+sizeof(blackY_)/sizeof(*blackY > 157 string _ = "NO"; > 158 END > 159 CASE(5) > 160 string whiteX_[] = {"219211 1996214 1706774 3634920 909831 1774128 8503" > 161 ,"52 2233050 2099138 3380396 1128982 3682525 1483700" > 162 ," 763080 487867 8203 1791027 463556 1103323 1406861" > 163 ," 6374234 760949 4340236 727393 2073832 1289052 103" > 164 ,"8147 4448130 151066 412440 1068735 377239 2677933 " > 165 ,"1299598 339843 289973 3707319 555280 230418 431719"}; > 166 vector <string> whiteX(whiteX_, whiteX_+sizeof(whiteX_)/sizeof(*whiteX > 167 string whiteY_[] = {"1638083 5698739 3105504 9726902 9745795 5049444 15" > 168 ,"80592 3952120 6606668 7460527 7239299 8726128 4913" > 169 ,"547 6264100 5701660 8865937 4969114 8014845 327236" > 170 ,"1 6389154 9739755 2561669 9412417 5452337 3150506 " > 171 ,"5832197 1571976 8779325 3306446 948271 5133709 949" > 172 ,"394 6919798 7525636 3568024 6833196 9237472 733313" > 173 ,"1 9939064 9720014"}; > 174 vector <string> whiteY(whiteY_, whiteY_+sizeof(whiteY_)/sizeof(*whiteY > 175 string blackX_[] = {"5860334 8007503 7455523 4864927 9573526 2718360 81" > 176 ,"12104 6684287 9921506 4840886 5415948 3451454 5320" > 177 ,"996 9268757 9261724 8254668 2292750 8035828 233352" > 178 ,"1 7676906 5234406 8533320 6562751 4884098 4971897 " > 179 ,"5569360 8519168 3100295 9351613 7733878 7579030 32" > 180 ,"46775 7297460 8370542 7099759 5782969 2978083 3390" > 181 ,"488 7482758 1332401 6094629 9717305 5503121 572842" > 182 ,"1 4903563 6331656 2867455 3410007 7751527 7228221 " > 183 ,"4111694 5171296 6847697 4601273 7599828 5515929 94" > 184 ,"60593 9332762 5389080 4512091 8668538 5711743 5838" > 185 ,"534 4825079 8145628 3810005 2964724 5594550 785748" > 186 ,"3 6283769"}; > 187 vector <string> blackX(blackX_, blackX_+sizeof(blackX_)/sizeof(*blackX > 188 string blackY_[] = {"5911694 8009943 212555 5838688 9896256 607434 5857" > 189 ,"663 4616750 1477573 7168026 3090917 4379806 326465" > 190 ,"7 4189076 2104028 3279691 94211 8503556 78457 4394" > 191 ,"360 3344176 3223317 2624498 4883494 1532240 732937" > 192 ,"1 1518674 1353567 892134 5536454 8527392 2603965 6" > 193 ,"623264 8830827 2030444 3002706 83058 4475866 20876" > 194 ,"25 1790695 4034441 5409379 3571098 4600050 736561 " > 195 ,"250475 3733256 3011439 2144994 4523046 3119883 607" > 196 ,"582 8361403 6525451 7518329 926803 4884524 8424659" > 197 ," 7088689 5762049 9532481 4914186 7314621 4339084 3" > 198 ,"741685 3837953 3177252 612550 9688871 5872931"}; > 199 vector <string> blackY(blackY_, blackY_+sizeof(blackY_)/sizeof(*blackY > 200 string _ = "YES"; > 201 END > 202 /* > 203 CASE(6) > 204 string whiteX_[] = ; > 205 vector <string> whiteX(whiteX_, whiteX_+sizeof(whiteX_)/sizeof(*whiteX > 206 string whiteY_[] = ; > 207 vector <string> whiteY(whiteY_, whiteY_+sizeof(whiteY_)/sizeof(*whiteY > 208 string blackX_[] = ; > 209 vector <string> blackX(blackX_, blackX_+sizeof(blackX_)/sizeof(*blackX > 210 string blackY_[] = ; > 211 vector <string> blackY(blackY_, blackY_+sizeof(blackY_)/sizeof(*blackY > 212 string _ = ; > 213 END > 214 CASE(7) > 215 string whiteX_[] = ; > 216 vector <string> whiteX(whiteX_, whiteX_+sizeof(whiteX_)/sizeof(*whiteX > 217 string whiteY_[] = ; > 218 vector <string> whiteY(whiteY_, whiteY_+sizeof(whiteY_)/sizeof(*whiteY > 219 string blackX_[] = ; > 220 vector <string> blackX(blackX_, blackX_+sizeof(blackX_)/sizeof(*blackX > 221 string blackY_[] = ; > 222 vector <string> blackY(blackY_, blackY_+sizeof(blackY_)/sizeof(*blackY > 223 string _ = ; > 224 END > 225 */ > 226 } > 227 // END CUT HERE
Added SRM/562-U/1C-U.cpp version [f4634643344316b4]
> 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 using namespace std; > 18 typedef long long LL; > 19 typedef long double LD; > 20 typedef complex<LD> CMP; > 21 > 22 static const unsigned MODVAL = 1000000009; > 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<mint> FAC_(1,1); > 39 mint FAC(LL n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*FAC_.size() > 40 > 41 // nCk :: O(1) time, O(n^2) space. > 42 vector< vector<mint> > CP_; > 43 mint C(LL n, LL k) { > 44 while( CP_.size() <= n ) { > 45 int nn = CP_.size(); > 46 CP_.push_back(vector<mint>(nn+1,1)); > 47 for(int kk=1; kk<nn; ++kk) > 48 CP_[nn][kk] = CP_[nn-1][kk-1] + CP_[nn-1][kk]; > 49 } > 50 return k<0 || n<k ? 0 : CP_[n][k]; > 51 } > 52 > 53 class InducedSubgraphs { public: > 54 int getCount(vector <int> edge1, vector <int> edge2, int k) > 55 { > 56 int N = edge1.size()+1; > 57 vector< vector<int> > G(N); > 58 for(int i=0; i<edge1.size(); ++i) > 59 { > 60 int v = edge1[i], u = edge2[i]; > 61 G[v].push_back(u); > 62 G[u].push_back(v); > 63 } > 64 return solve(G, N, k).val; > 65 } > 66 > 67 mint solve(const vector<vector<int> >& G, int N, int K) > 68 { > 69 mint total = 0; > 70 for(int root=0; root<N; ++root) > 71 total += solve_rooted(G, N, K, root); > 72 return total; > 73 } > 74 > 75 mint solve_rooted(const vector<vector<int> >& G, int N, int K, int root) > 76 { > 77 memo.clear(); > 78 > 79 int pre = -1, cur = root; > 80 for(int below=N,above=0 ;; --below,++above) > 81 if(below <= K) { > 82 mint b = rec(G, pre, cur).second; > 83 mint a = (above>=K-1 ? mint(1) : FAC(K-above)); > 84 return b*a; > 85 } else { > 86 if((pre==-1 && G[cur].size()>=2) || G[cur].size( > 87 // fill_branch > 88 /* > 89 vector< pair<int,int> > v_sz; > 90 for(int k=0; k<G[cur].size(); ++k) if(G[ > 91 v_sz.push_back(make_pair(G[cur][ > 92 > 93 int total_size = 0; > 94 for(int k=0; k<v_sz.size(); ++k) > 95 total_size += v_sz[k].second; > 96 for(int k=0; k<v_sz.size(); ++k) > 97 if( v_sz[k].second+1 <= K ) > 98 */ > 99 return 0; > 100 } > 101 > 102 int nex = (G[cur][0]!=pre ? G[cur][0] : G[cur][1 > 103 pre = cur; > 104 cur = nex; > 105 } > 106 } > 107 > 108 // (size, number of toplofical sorting). > 109 map<int, pair<int,mint> > memo; > 110 pair<int,mint> rec(const vector<vector<int> >& G, int pre, int cur) > 111 { > 112 if(memo.count(cur)) > 113 return memo[cur]; > 114 > 115 vector< pair<int,mint> > children; > 116 for(int i=0; i<G[cur].size(); ++i) if(G[cur][i] != pre) > 117 children.push_back(rec(G, cur, G[cur][i])); > 118 > 119 mint pat = 1; > 120 int size = 0; > 121 for(int i=0; i<children.size(); ++i) { > 122 size += children[i].first; > 123 pat = pat * C(size, children[i].first) * children[i].s > 124 } > 125 return memo[cur] = make_pair(size+1, pat); > 126 } > 127 }; > 128 > 129 // BEGIN CUT HERE > 130 #include <ctime> > 131 double start_time; string timer() > 132 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 133 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 134 { os << "{ "; > 135 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 136 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 137 void verify_case(const int& Expected, const int& Received) { > 138 bool ok = (Expected == Received); > 139 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 140 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 141 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 142 #define END verify_case(_, InducedSubgraphs().getCount(edge1, edge2, k));} > 143 int main(){ > 144 > 145 CASE(0) > 146 int edge1_[] = {0, 1}; > 147 vector <int> edge1(edge1_, edge1_+sizeof(edge1_)/sizeof(*edge1_)); > 148 int edge2_[] = {1, 2}; > 149 vector <int> edge2(edge2_, edge2_+sizeof(edge2_)/sizeof(*edge2_)); > 150 int k = 2; > 151 int _ = 2; > 152 END > 153 CASE(1) > 154 int edge1_[] = {0, 1, 3}; > 155 vector <int> edge1(edge1_, edge1_+sizeof(edge1_)/sizeof(*edge1_)); > 156 int edge2_[] = {2, 2, 2}; > 157 vector <int> edge2(edge2_, edge2_+sizeof(edge2_)/sizeof(*edge2_)); > 158 int k = 3; > 159 int _ = 12; > 160 END > 161 CASE(2) > 162 int edge1_[] = {5, 0, 1, 2, 2}; > 163 vector <int> edge1(edge1_, edge1_+sizeof(edge1_)/sizeof(*edge1_)); > 164 int edge2_[] = {0, 1, 2, 4, 3}; > 165 vector <int> edge2(edge2_, edge2_+sizeof(edge2_)/sizeof(*edge2_)); > 166 int k = 3; > 167 int _ = 4; > 168 END > 169 CASE(3) > 170 int edge1_[] = {0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6}; > 171 vector <int> edge1(edge1_, edge1_+sizeof(edge1_)/sizeof(*edge1_)); > 172 int edge2_[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14}; > 173 vector <int> edge2(edge2_, edge2_+sizeof(edge2_)/sizeof(*edge2_)); > 174 int k = 11; > 175 int _ = 481904640; > 176 END > 177 CASE(4) > 178 int edge1_[] = {5, 9, 4, 10, 10, 0, 7, 6, 2, 1, 11, 8} > 179 ; > 180 vector <int> edge1(edge1_, edge1_+sizeof(edge1_)/sizeof(*edge1_)); > 181 int edge2_[] = {0, 0, 10, 3, 0, 6, 1, 1, 12, 12, 7, 11} > 182 ; > 183 vector <int> edge2(edge2_, edge2_+sizeof(edge2_)/sizeof(*edge2_)); > 184 int k = 6; > 185 int _ = 800; > 186 END > 187 CASE(5) > 188 int edge1_[] = {0, 5, 1, 0, 2, 3, 5} > 189 ; > 190 vector <int> edge1(edge1_, edge1_+sizeof(edge1_)/sizeof(*edge1_)); > 191 int edge2_[] = {4, 7, 0, 6, 7, 5, 0} > 192 ; > 193 vector <int> edge2(edge2_, edge2_+sizeof(edge2_)/sizeof(*edge2_)); > 194 int k = 3; > 195 int _ = 0; > 196 END > 197 CASE(6) > 198 int edge1_[] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}; > 199 vector <int> edge1(edge1_, edge1_+sizeof(edge1_)/sizeof(*edge1_)); > 200 int edge2_[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}; > 201 vector <int> edge2(edge2_, edge2_+sizeof(edge2_)/sizeof(*edge2_)); > 202 int k = 1; > 203 int _ = 890964601; > 204 END > 205 /* > 206 CASE(7) > 207 int edge1_[] = ; > 208 vector <int> edge1(edge1_, edge1_+sizeof(edge1_)/sizeof(*edge1_)); > 209 int edge2_[] = ; > 210 vector <int> edge2(edge2_, edge2_+sizeof(edge2_)/sizeof(*edge2_)); > 211 int k = ; > 212 int _ = ; > 213 END > 214 CASE(8) > 215 int edge1_[] = ; > 216 vector <int> edge1(edge1_, edge1_+sizeof(edge1_)/sizeof(*edge1_)); > 217 int edge2_[] = ; > 218 vector <int> edge2(edge2_, edge2_+sizeof(edge2_)/sizeof(*edge2_)); > 219 int k = ; > 220 int _ = ; > 221 END > 222 */ > 223 } > 224 // END CUT HERE