Overview
| SHA1 Hash: | 257929a5e91e15337c0217f3b0d4ef1736041379 |
|---|---|
| Date: | 2013-01-21 11:25:29 |
| User: | kinaba |
| Comment: | 566 |
| 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/566-U/1A.cpp version [1342371824ba4cfe]
> 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 LL comb(LL n, LL k) > 23 { > 24 k = min(k, n-k); > 25 > 26 LL c = 1; > 27 for(LL i=0; i<k; ++i) > 28 c *= n-i, c /= i+1; > 29 return c; > 30 } > 31 > 32 class PenguinSledding { public: > 33 long long countDesigns(int numCheckpoints, vector <int> checkpoint1, vec > 34 { > 35 LL zero = 1; > 36 LL one = checkpoint1.size(); > 37 LL star = 0; > 38 LL triangle = 0; > 39 > 40 for(int center=1; center<=numCheckpoints; ++center) { > 41 int leaf = 0; > 42 for(int i=0; i<checkpoint1.size(); ++i) > 43 if(checkpoint1[i] == center) > 44 ++leaf; > 45 else if(checkpoint2[i] == center) > 46 ++leaf; > 47 for(int k=2; k<=leaf; ++k) > 48 star += comb(leaf, k); > 49 } > 50 > 51 set< pair<int,int> > conn; > 52 for(int i=0; i<checkpoint1.size(); ++i) { > 53 conn.insert(make_pair(checkpoint1[i], checkpoint2[i])); > 54 conn.insert(make_pair(checkpoint2[i], checkpoint1[i])); > 55 } > 56 for(int a=1; a<=numCheckpoints; ++a) > 57 for(int b=a+1; b<=numCheckpoints; ++b) > 58 for(int c=b+1; c<=numCheckpoints; ++c) > 59 if(conn.count(make_pair(a,b)) && conn.count(make_pair(b, > 60 ++triangle; > 61 > 62 return zero + one + star + triangle; > 63 } > 64 }; > 65 > 66 // BEGIN CUT HERE > 67 #include <ctime> > 68 double start_time; string timer() > 69 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 70 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 71 { os << "{ "; > 72 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 73 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 74 void verify_case(const long long& Expected, const long long& Received) { > 75 bool ok = (Expected == Received); > 76 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 77 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 78 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 79 #define END verify_case(_, PenguinSledding().countDesigns(numCheckpoints, c > 80 int main(){ > 81 > 82 CASE(0) > 83 int numCheckpoints = 2; > 84 int checkpoint1_[] = {1}; > 85 vector <int> checkpoint1(checkpoint1_, checkpoint1_+sizeof(checkpoint1 > 86 int checkpoint2_[] = {2}; > 87 vector <int> checkpoint2(checkpoint2_, checkpoint2_+sizeof(checkpoint2 > 88 long long _ = 2LL; > 89 END > 90 CASE(1) > 91 int numCheckpoints = 4; > 92 int checkpoint1_[] = {1,2,3}; > 93 vector <int> checkpoint1(checkpoint1_, checkpoint1_+sizeof(checkpoint1 > 94 int checkpoint2_[] = {2,3,4}; > 95 vector <int> checkpoint2(checkpoint2_, checkpoint2_+sizeof(checkpoint2 > 96 long long _ = 6LL; > 97 END > 98 CASE(2) > 99 int numCheckpoints = 6; > 100 int checkpoint1_[] = {1,3,6}; > 101 vector <int> checkpoint1(checkpoint1_, checkpoint1_+sizeof(checkpoint1 > 102 int checkpoint2_[] = {2,4,4}; > 103 vector <int> checkpoint2(checkpoint2_, checkpoint2_+sizeof(checkpoint2 > 104 long long _ = 5LL; > 105 END > 106 CASE(3) > 107 int numCheckpoints = 50; > 108 int checkpoint1_[] = {40, 40, 40, 40, 40, 40, 40, 40, > 109 40, 40, 40, 40, 50, 40, 40, 40, > 110 23, 4, 24, 40, 22, 40, 8, 40, 40, > 111 40, 34, 21, 40, 40, 38, 40, 40, > 112 40, 40, 40, 28, 40, 40, 40, 40, > 113 46, 13, 40, 40, 40, 47, 40, 40}; > 114 vector <int> checkpoint1(checkpoint1_, checkpoint1_+sizeof(checkpoint1 > 115 int checkpoint2_[] = {45, 42, 20, 48, 12, 32, 25, 10, > 116 26, 39, 16, 2, 19, 43, 37, 17, > 117 19, 19, 19, 18, 19, 27, 19, 29, > 118 11, 36, 19, 19, 1, 41, 19, 35, > 119 14, 33, 49, 3, 19, 7, 5, 19, 31, > 120 19, 19, 6, 9, 15, 19, 44, 30}; > 121 vector <int> checkpoint2(checkpoint2_, checkpoint2_+sizeof(checkpoint2 > 122 long long _ = 68719493118LL; > 123 END > 124 CASE(4) > 125 int numCheckpoints = 36; > 126 int checkpoint1_[] = {13, 24, 24, 20, 31, 16, 10, 36, 34, 32, > 127 28, 5, 20, 29, 23, 2, 14, 4, 9, 5, 19, > 128 21, 8, 1, 26, 27, 25, 15, 22, 30, 30, > 129 6, 11, 7, 2, 35, 13, 29, 4, 12, 33, 18, > 130 13, 14, 17, 35, 3}; > 131 vector <int> checkpoint1(checkpoint1_, checkpoint1_+sizeof(checkpoint1 > 132 int checkpoint2_[] = {10, 15, 27, 1, 29, 11, 5, 18, 33, 1, 9, > 133 2, 31, 6, 19, 10, 33, 18, 6, 27, 3, 22, > 134 4, 12, 31, 30, 34, 16, 7, 24, 3, 28, 15, > 135 21, 22, 8, 26, 20, 14, 32, 25, 17, 35, > 136 8, 36, 26, 23}; > 137 vector <int> checkpoint2(checkpoint2_, checkpoint2_+sizeof(checkpoint2 > 138 long long _ = 162LL; > 139 END > 140 /* > 141 CASE(5) > 142 int numCheckpoints = ; > 143 int checkpoint1_[] = ; > 144 vector <int> checkpoint1(checkpoint1_, checkpoint1_+sizeof(checkpoint1 > 145 int checkpoint2_[] = ; > 146 vector <int> checkpoint2(checkpoint2_, checkpoint2_+sizeof(checkpoint2 > 147 long long _ = LL; > 148 END > 149 CASE(6) > 150 int numCheckpoints = ; > 151 int checkpoint1_[] = ; > 152 vector <int> checkpoint1(checkpoint1_, checkpoint1_+sizeof(checkpoint1 > 153 int checkpoint2_[] = ; > 154 vector <int> checkpoint2(checkpoint2_, checkpoint2_+sizeof(checkpoint2 > 155 long long _ = LL; > 156 END > 157 */ > 158 } > 159 // END CUT HERE
Added SRM/566-U/1B.cpp version [770f87bd162c875d]
> 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 = 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 = LL(x.val)*y.val; } > 33 mint operator+(mint x, mint y) { return x+=y; } > 34 mint operator*(mint x, mint y) { return x*=y; } > 35 > 36 template<typename T> > 37 vector<T> MATMULxx(const vector<T>& a, const vector<T>& v) > 38 { > 39 int N = a.size(); > 40 vector<T> u(N); > 41 for(int i=0; i<N; ++i) > 42 for(int j=0; j<N; ++j) > 43 u[i] += a[(j-i+N)%N]*v[j]; > 44 return u; > 45 } > 46 > 47 template<typename T> > 48 vector<T> MATMULxx(const vector<T>& a) > 49 { > 50 int N = a.size(); > 51 vector<T> c(N); > 52 for(int j=0; j<N; ++j) > 53 for(int k=0; k<N; ++k) > 54 c[j] += a[k]*a[(j-k+N)%N]; > 55 return c; > 56 } > 57 > 58 template<typename T> > 59 vector<T> MATPOWMULxx(vector<T> a, LL e, vector<T> v) > 60 { > 61 for(; e; e>>=1, a=MATMULxx(a)) > 62 if(e&1) > 63 v = MATMULxx(a, v); > 64 return v; > 65 } > 66 > 67 class PenguinEmperor { public: > 68 int countJourneys(int N, long long daysPassed) > 69 { > 70 vector<mint> v(N), u(N); > 71 u[0] = 1; > 72 for(int i=0; i<N; ++i) { > 73 if(i == daysPassed % N) > 74 v = u; > 75 vector<mint> uu(N); > 76 for(int x=0; x<N; ++x) { > 77 int f = (x+i+1)%N; > 78 int b = (x-i-1+N)%N; > 79 uu[x] += u[f]; > 80 if(f!=b) > 81 uu[x] += u[b]; > 82 } > 83 u = uu; > 84 } > 85 > 86 v = MATPOWMULxx(u, daysPassed/N, v); > 87 return v[0].val; > 88 } > 89 }; > 90 > 91 // BEGIN CUT HERE > 92 #include <ctime> > 93 double start_time; string timer() > 94 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 95 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 96 { os << "{ "; > 97 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 98 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 99 void verify_case(const int& Expected, const int& Received) { > 100 bool ok = (Expected == Received); > 101 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 102 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 103 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 104 #define END verify_case(_, PenguinEmperor().countJourneys(numCities, daysPa > 105 int main(){ > 106 > 107 CASE(0) > 108 int numCities = 3; > 109 long long daysPassed = 2LL; > 110 int _ = 2; > 111 END > 112 CASE(1) > 113 int numCities = 4; > 114 long long daysPassed = 3LL; > 115 int _ = 2; > 116 END > 117 CASE(2) > 118 int numCities = 5; > 119 long long daysPassed = 36LL; > 120 int _ = 107374182; > 121 END > 122 CASE(3) > 123 int numCities = 300; > 124 long long daysPassed = 751LL; > 125 int _ = 413521250; > 126 END > 127 CASE(4) > 128 int numCities = 300; > 129 long long daysPassed = 750LL; > 130 int _ = 0; > 131 END > 132 CASE(5) > 133 int numCities = 350; > 134 long long daysPassed = 1000000000000000000LL; > 135 int _ = 667009739; > 136 END > 137 CASE(6) > 138 int numCities = 5; > 139 long long daysPassed = 7LL; > 140 int _ = 12; > 141 END > 142 /* > 143 CASE(7) > 144 int numCities = ; > 145 long long daysPassed = LL; > 146 int _ = ; > 147 END > 148 CASE(8) > 149 int numCities = ; > 150 long long daysPassed = LL; > 151 int _ = ; > 152 END > 153 */ > 154 } > 155 // END CUT HERE
Modified lib/doc/nim.txt from [afa6596dc04e5d36] to [a6c762d68e00b3ce].
56 -------------------------------------------------------------------------------- 56 -------------------------------------------------------------------------------- 57 定理【ゲームの和はxor】 57 定理【ゲームの和はxor】 58 - *n1 + *n2 = *(n1 xor n2) 58 - *n1 + *n2 = *(n1 xor n2) 59 - より一般的に G1≡*n1, G2≡*n2 ならば、G1 + G2 ≡ *(n1 xor n2) 59 - より一般的に G1≡*n1, G2≡*n2 ならば、G1 + G2 ≡ *(n1 xor n2) 60 60 61 証明 61 証明 62 - *n1 + *n2 + *(n1 xor n2) が必敗であることを言えば良い。 62 - *n1 + *n2 + *(n1 xor n2) が必敗であることを言えば良い。 63 < > 63 - (n1 xor n2 xor (n1 xor n2)) は 0 である > 64 - 一手動かすと 0 じゃなくなる > 65 >> n1 と n2 と n1^n2 のどれか一個だけビットが変わるの絶対xorが変わるから > 66 - 相手は一手動かして 0 に戻せる > 67 >> 常に > 68 - よって最終局面"全部 0"になるのは絶対に自分のターン 64 69 65 70 66 -------------------------------------------------------------------------------- 71 -------------------------------------------------------------------------------- 67 定理【ゲームの状態遷移はmex】 72 定理【ゲームの状態遷移はmex】 68 - {*n1, ..., *nk} ≡ *mex(n1,...,nk) 73 - {*n1, ..., *nk} ≡ *mex(n1,...,nk) 69 where mex(S) = min(nat \setminus S) 74 where mex(S) = min(nat \setminus S) 70 75