Overview
| SHA1 Hash: | 092758c493d47b1da386430fd5fc34bfa963228c |
|---|---|
| Date: | 2015-01-16 01:56:09 |
| User: | kinaba |
| Comment: | 644 |
| 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/644-U/1A.cpp version [938cf19239478dda]
> 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_.si > 44 > 45 mint C(LL n, LL k) { return k<0 || n<k ? 0 : FAC(n) / (FAC(k) * FAC(n-k)); } > 46 > 47 class OkonomiyakiParty { public: > 48 int count(vector <int> osize, int M, int K) > 49 { > 50 mint ans = 0; > 51 > 52 sort(osize.begin(), osize.end()); > 53 for(int s=0; s<osize.size(); ++s) > 54 for(int e=s; e<osize.size(); ++e) > 55 if( osize[e]-osize[s]<=K ) > 56 ans += C(e-s-1, M-2); > 57 > 58 return ans.val; > 59 } > 60 }; > 61 > 62 // BEGIN CUT HERE > 63 #include <ctime> > 64 double start_time; string timer() > 65 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 66 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 67 { os << "{ "; > 68 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 69 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 70 void verify_case(const int& Expected, const int& Received) { > 71 bool ok = (Expected == Received); > 72 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 73 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 74 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 75 #define END verify_case(_, OkonomiyakiParty().count(osize, M, K));} > 76 int main(){ > 77 > 78 CASE(0) > 79 int osize_[] = {1,4,6,7,9}; > 80 vector <int> osize(osize_, osize_+sizeof(osize_)/sizeof(*osize_)); > 81 int M = 2; > 82 int K = 3; > 83 int _ = 6; > 84 END > 85 CASE(1) > 86 int osize_[] = {1,6,2,7,4,2,6,1,5,2,4}; > 87 vector <int> osize(osize_, osize_+sizeof(osize_)/sizeof(*osize_)); > 88 int M = 4; > 89 int K = 3; > 90 int _ = 60; > 91 END > 92 CASE(2) > 93 int osize_[] = {1,4,5,7,10,11,13,16,18}; > 94 vector <int> osize(osize_, osize_+sizeof(osize_)/sizeof(*osize_)); > 95 int M = 4; > 96 int K = 5; > 97 int _ = 0; > 98 END > 99 CASE(3) > 100 int osize_[] = {55,2,7,232,52,5,5332,623,52,6,532,5147}; > 101 vector <int> osize(osize_, osize_+sizeof(osize_)/sizeof(*osize_)); > 102 int M = 6; > 103 int K = 10000; > 104 int _ = 924; > 105 END > 106 CASE(4) > 107 int osize_[] = {5781,8708,1754,4750,9888,3675,4810,1020,922,9834,5695,11 > 108 1376,3373,4423,1839,7438,9407,1851,6966,8715,2905,542,535,8980,2602,2603,3117,34 > 109 5682,7775,4356,5140,8923,9801,3729}; > 110 vector <int> osize(osize_, osize_+sizeof(osize_)/sizeof(*osize_)); > 111 int M = 15; > 112 int K = 4003; > 113 int _ = 114514; > 114 END > 115 /* > 116 CASE(5) > 117 int osize_[] = ; > 118 vector <int> osize(osize_, osize_+sizeof(osize_)/sizeof(*osize_)); > 119 int M = ; > 120 int K = ; > 121 int _ = ; > 122 END > 123 CASE(6) > 124 int osize_[] = ; > 125 vector <int> osize(osize_, osize_+sizeof(osize_)/sizeof(*osize_)); > 126 int M = ; > 127 int K = ; > 128 int _ = ; > 129 END > 130 */ > 131 } > 132 // END CUT HERE