Overview
| SHA1 Hash: | 2781d1e6162e67286e1e103ff423953b5667db42 |
|---|---|
| Date: | 2016-07-09 15:22:26 |
| User: | kinaba |
| Comment: | TCO |
| 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/TCO16-2C-U/1A.cpp version [7ceaf0a4b86ab15e]
cannot compute difference between binary files
Added SRM/TCO16-2C-U/1B-U.cpp version [86bec40a9221e580]
> 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 int K; > 23 > 24 static const unsigned MODVAL = 1000000007; > 25 struct mint > 26 { > 27 unsigned val; > 28 mint():val(0){} > 29 mint(int x):val(x%MODVAL) {} > 30 mint(unsigned x):val(x%MODVAL) {} > 31 mint(LL x):val(x%MODVAL) {} > 32 }; > 33 mint& operator+=(mint& x, mint y) { return x = x.val+y.val; } > 34 mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; } > 35 mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; } > 36 mint operator+(mint x, mint y) { return x+=y; } > 37 mint operator-(mint x, mint y) { return x-=y; } > 38 mint operator*(mint x, mint y) { return x*=y; } > 39 > 40 mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; } > 41 mint& operator/=(mint& x, mint y) { return x *= POW(y, MODVAL-2); } > 42 mint operator/(mint x, mint y) { return x/=y; } > 43 > 44 vector<mint> solve(int N, vector<mint> q) > 45 { > 46 if(N == 1) > 47 return vector<mint>(1, mint(1)); > 48 > 49 vector<mint> p(N); > 50 for(int s=0; s<N; ++s) { > 51 int d = ((N+1-K)%N+N)%N; > 52 if(s == d) { > 53 p[s] = 2 * (d<N-1 ? q[d]/2 : mint(0)); > 54 break; > 55 } > 56 } > 57 for(int s=0; s<N; ++s) { > 58 int d = ((N+1-K)%N+N)%N; > 59 if(s != d) { > 60 p[s] = p[d]/2 + (d<N-1 ? q[d]/2 : mint(0)); > 61 } > 62 } > 63 return p; > 64 } > 65 > 66 class BearCircleGame { public: > 67 int winProbability(int n, int k) > 68 { > 69 K = k; > 70 vector<mint> p; > 71 for(int nn=1; nn<=n; ++nn) > 72 p = solve(nn, p); > 73 return p[0].val; > 74 } > 75 }; > 76 > 77 // BEGIN CUT HERE > 78 #include <ctime> > 79 double start_time; string timer() > 80 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 81 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 82 { os << "{ "; > 83 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 84 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 85 void verify_case(const int& Expected, const int& Received) { > 86 bool ok = (Expected == Received); > 87 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 88 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 89 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 90 #define END verify_case(_, BearCircleGame().winProbability(n, k));} > 91 int main(){ > 92 > 93 CASE(0) > 94 int n = 2; > 95 int k = 1; > 96 int _ = 333333336; > 97 END > 98 CASE(1) > 99 int n = 2; > 100 int k = 2; > 101 int _ = 1; > 102 END > 103 CASE(2) > 104 int n = 3; > 105 int k = 2; > 106 int _ = 142857144; > 107 END > 108 CASE(3) > 109 int n = 3; > 110 int k = 1; > 111 int _ = 238095240; > 112 END > 113 CASE(4) > 114 int n = 4; > 115 int k = 4; > 116 int _ = 142857144; > 117 END > 118 CASE(5) > 119 int n = 5; > 120 int k = 1000000000; > 121 int _ = 142857144; > 122 END > 123 CASE(6) > 124 int n = 2000; > 125 int k = 123; > 126 int _ = 429232785; > 127 END > 128 CASE(7) > 129 int n = 1987; > 130 int k = 987654321; > 131 int _ = 623410299; > 132 END > 133 /* > 134 CASE(8) > 135 int n = ; > 136 int k = ; > 137 int _ = ; > 138 END > 139 CASE(9) > 140 int n = ; > 141 int k = ; > 142 int _ = ; > 143 END > 144 */ > 145 } > 146 // END CUT HERE