Overview
| SHA1 Hash: | ba4cf1f68f556f16a826662333a60fddf962d40e |
|---|---|
| Date: | 2019-07-19 00:57:41 |
| User: | kinaba |
| Comment: | TCO193A |
| 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/TCO19-3A-U/1A.cpp version [502bd2f362b9242b]
> 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 mint POW(mint x, LL e) { mint v = 1; for (; e; x *= x, e >>= 1) if (e & 1) v *= > 39 mint& operator/=(mint& x, mint y) { return x *= POW(y, MODVAL - 2); } > 40 mint operator/(mint x, mint y) { return x /= y; } > 41 > 42 vector<mint> FAC_(1, 1); > 43 mint FAC(LL n) { while (FAC_.size() <= n) FAC_.push_back(FAC_.back()*LL(FAC_.siz > 44 > 45 vector< vector<mint> > CP_; > 46 mint C(int n, int k) { > 47 while (CP_.size() <= n) { > 48 int nn = CP_.size(); > 49 CP_.push_back(vector<mint>(nn + 1, 1)); > 50 for (int kk = 1; kk<nn; ++kk) > 51 CP_[nn][kk] = CP_[nn - 1][kk - 1] + CP_[nn - 1][kk]; > 52 } > 53 return k<0 || n<k ? 0 : CP_[n][k]; > 54 } > 55 > 56 vector< vector<mint> > SP_; > 57 mint S(int n, int k) { > 58 while (SP_.size() <= n) { > 59 int nn = SP_.size(); > 60 SP_.push_back(vector<mint>(nn + 1, 1)); > 61 for (int kk = 2; kk<nn; ++kk) > 62 SP_[nn][kk] = SP_[nn - 1][kk - 1] + kk*SP_[nn - 1][kk]; > 63 } > 64 return k<=0 || n<k ? 0 : SP_[n][k]; > 65 } > 66 > 67 class FamilySeatingArrangement { public: > 68 int countWays(vector <int> a, int k) > 69 { > 70 const int f = int(a.size()); > 71 const int nc = accumulate(a.begin(), a.end(), 0); > 72 mint ans = 0; > 73 for (int parentTable = 1; parentTable <= min(f, k); ++parentTabl > 74 ans += POW(k - parentTable + 1, nc) * C(k, parentTable) > 75 return ans.val; > 76 } > 77 > 78 // |p| people to |t| tables > 79 mint countParentWays(int p, int t) > 80 { > 81 return S(p, t) * FAC(t); > 82 } > 83 }; > 84 > 85 // BEGIN CUT HERE > 86 #include <ctime> > 87 double start_time; string timer() > 88 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 89 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 90 { os << "{ "; > 91 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 92 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 93 void verify_case(const int& Expected, const int& Received) { > 94 bool ok = (Expected == Received); > 95 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 96 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 97 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 98 #define END verify_case(_, FamilySeatingArrangement().countWays(a, k));} > 99 int main(){ > 100 > 101 CASE(0) > 102 int a_[] = {2,1} ; > 103 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 104 int k = 2; > 105 int _ = 18; > 106 END > 107 CASE(1) > 108 int a_[] = {2,1}; > 109 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 110 int k = 3; > 111 int _ = 129; > 112 END > 113 CASE(2) > 114 int a_[] = {2,1}; > 115 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 116 int k = 1000; > 117 int _ = 989021965; > 118 END > 119 CASE(3) > 120 int a_[] = {1,1,1,1,1,1,1,1,1,1,1,1}; > 121 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 122 int k = 8; > 123 int _ = 604306839; > 124 END > 125 CASE(4) > 126 int a_[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20} ; > 127 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 128 int k = 211; > 129 int _ = 775937801; > 130 END > 131 CASE(5) > 132 int a_[] = { 1 }; > 133 vector <int> a(a_, a_ + sizeof(a_) / sizeof(*a_)); > 134 int k = 2; > 135 int _ = 4; > 136 END > 137 CASE(6) > 138 int a_[] = { 1 }; > 139 vector <int> a(a_, a_ + sizeof(a_) / sizeof(*a_)); > 140 int k = 1; > 141 int _ = 1; > 142 END > 143 CASE(7) > 144 int a_[] = { > 145 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 146 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 147 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 148 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 149 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 150 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 151 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 152 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 153 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 154 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 155 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 156 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 157 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 158 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 159 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 160 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 161 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 162 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 163 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 164 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 165 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 166 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 167 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 168 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 169 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 170 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 171 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 172 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 173 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 174 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 175 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 176 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 177 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 178 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 179 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 180 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 181 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 182 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 183 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 184 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 185 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 186 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 187 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 188 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 189 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 190 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 191 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 192 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 193 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 194 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 195 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 196 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 197 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 198 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 199 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 200 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 201 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 202 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 203 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 204 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 205 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 206 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 207 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 208 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 209 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 210 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 211 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 212 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 213 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 214 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 215 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 216 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 217 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 218 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 219 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 220 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 221 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 222 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 223 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 224 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 225 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 226 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 227 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 228 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 229 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 230 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 231 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 232 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 233 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 234 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 235 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 236 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 237 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 238 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 239 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 240 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 241 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 242 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 243 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 244 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000 }; > 245 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 246 int k = 1000; > 247 int _ = -1; > 248 END > 249 } > 250 // END CUT HERE