Check-in [ba4cf1f68f]
Not logged in
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
Changes
hide diffs side-by-side diffs patch

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 *= x; return 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_.size())); return FAC_[n]; }
           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); ++parentTable)
           74  +   ans += POW(k - parentTable + 1, nc) * C(k, parentTable) * countParentWays(f, 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) << " msec)"; return os.str(); }
           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 os; }
           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() << endl;
           96  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           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

Fossil version [8d758d3715] 2012-10-22 12:48:04