Overview
| SHA1 Hash: | 2de557d8c07b2ec5d2dd216b89007bf794521e3b |
|---|---|
| Date: | 2011-03-20 00:13:20 |
| User: | kinaba |
| Comment: | 499 |
| 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
Modified CheckList.pptx from [41156cd7a947e2a7] to [dcb9bdddd36bb3bb].
cannot compute difference between binary files
Added SRM/398/2C.cpp version [f85d7cb8c1261a54]
> 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 <cstring> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 class MatchString { public: > 23 int placeWords(string matchString, vector <string> matchWords) > 24 { > 25 const int N = matchString.size(); > 26 vector< vector<int> > idx(N); > 27 set<int> all_idx; > 28 > 29 for(int i=0; i<N; ++i) > 30 { > 31 for(int j=0; j<matchWords[i].size(); ++j) > 32 if( matchWords[i][j] == matchString[i] ) > 33 { > 34 idx[i].push_back(j); > 35 all_idx.insert(j); > 36 } > 37 if( idx[i].empty() ) > 38 return -1; > 39 } > 40 > 41 int best = INT_MAX; > 42 for(set<int>::iterator it=all_idx.begin(); it!=all_idx.end(); ++ > 43 { > 44 int T = *it; > 45 int score = 0; > 46 for(int i=0; i<N; ++i) > 47 { > 48 int bb = INT_MAX; > 49 for(int j=0; j<idx[i].size(); ++j) > 50 if( idx[i][j] <= T ) > 51 bb = min(bb, T-idx[i][j]); > 52 if( bb == INT_MAX ) > 53 goto next; > 54 score += bb; > 55 } > 56 best = min(best, score); > 57 next:; > 58 } > 59 return best; > 60 } > 61 }; > 62 > 63 // BEGIN CUT HERE > 64 #include <ctime> > 65 double start_time; string timer() > 66 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 67 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 68 { os << "{ "; > 69 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 70 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 71 void verify_case(const int& Expected, const int& Received) { > 72 bool ok = (Expected == Received); > 73 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 74 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 75 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 76 #define END verify_case(_, MatchString().placeWords(matchString, matchWords > 77 int main(){ > 78 > 79 CASE(0) > 80 string matchString = "TOP"; > 81 string matchWords_[] = {"TIK", > 82 "PPPO", > 83 "OP"}; > 84 vector <string> matchWords(matchWords_, matchWords_+sizeof(matchWords_ > 85 int _ = 5; > 86 END > 87 CASE(1) > 88 string matchString = "EEA"; > 89 string matchWords_[] = {"GEGA", > 90 "TOPCODER", > 91 "TEST"}; > 92 vector <string> matchWords(matchWords_, matchWords_+sizeof(matchWords_ > 93 int _ = -1; > 94 END > 95 CASE(2) > 96 string matchString = "AB"; > 97 string matchWords_[] = {"ABA", > 98 "ABAB"}; > 99 vector <string> matchWords(matchWords_, matchWords_+sizeof(matchWords_ > 100 int _ = 1; > 101 END > 102 CASE(3) > 103 string matchString = "FIND"; > 104 string matchWords_[] = {"VERYFAST", > 105 "OPINION", > 106 "SPENDING", > 107 "ODD"}; > 108 vector <string> matchWords(matchWords_, matchWords_+sizeof(matchWords_ > 109 int _ = 3; > 110 END > 111 CASE(4) > 112 string matchString = "TOP"; > 113 string matchWords_[] = {"OUTTHERE", > 114 "FROM", > 115 "NOPQRSTU"}; > 116 vector <string> matchWords(matchWords_, matchWords_+sizeof(matchWords_ > 117 int _ = 0; > 118 END > 119 /* > 120 CASE(5) > 121 string matchString = ; > 122 string matchWords_[] = ; > 123 vector <string> matchWords(matchWords_, matchWords_+sizeof(matchWords_ > 124 int _ = ; > 125 END > 126 CASE(6) > 127 string matchString = ; > 128 string matchWords_[] = ; > 129 vector <string> matchWords(matchWords_, matchWords_+sizeof(matchWords_ > 130 int _ = ; > 131 END > 132 */ > 133 } > 134 // END CUT HERE
Added SRM/499-U/1A.cpp version [1b6c222f9c3582e7]
> 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 <cstring> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 class ColorfulRabbits { public: > 23 int getMinimum(vector <int> replies) > 24 { > 25 map<int,int> m; > 26 for(int i=0; i<replies.size(); ++i) > 27 m[replies[i]]++; > 28 int total = 0; > 29 for(map<int,int>::iterator it=m.begin(); it!=m.end(); ++it) > 30 { > 31 int s = it->first + 1; > 32 int n = it->second; > 33 total += (n+s-1) / s * s; > 34 } > 35 return total; > 36 } > 37 }; > 38 > 39 // BEGIN CUT HERE > 40 #include <ctime> > 41 double start_time; string timer() > 42 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 43 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 44 { os << "{ "; > 45 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 46 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 47 void verify_case(const int& Expected, const int& Received) { > 48 bool ok = (Expected == Received); > 49 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 50 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 51 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 52 #define END verify_case(_, ColorfulRabbits().getMinimum(replies));} > 53 int main(){ > 54 > 55 CASE(0) > 56 int replies_[] = { 1, 1, 2, 2 } > 57 ; > 58 vector <int> replies(replies_, replies_+sizeof(replies_)/sizeof(*repli > 59 int _ = 5; > 60 END > 61 CASE(1) > 62 int replies_[] = { 0 } > 63 ; > 64 vector <int> replies(replies_, replies_+sizeof(replies_)/sizeof(*repli > 65 int _ = 1; > 66 END > 67 CASE(2) > 68 int replies_[] = { 2, 2, 44, 2, 2, 2, 444, 2, 2 } > 69 ; > 70 vector <int> replies(replies_, replies_+sizeof(replies_)/sizeof(*repli > 71 int _ = 499; > 72 END > 73 CASE(3) > 74 int replies_[] = {1}; > 75 vector <int> replies(replies_, replies_+sizeof(replies_)/sizeof(*repli > 76 int _ = 2; > 77 END > 78 CASE(4) > 79 int replies_[] = {2}; > 80 vector <int> replies(replies_, replies_+sizeof(replies_)/sizeof(*repli > 81 int _ = 3; > 82 END > 83 CASE(5) > 84 int replies_[] = {1000000,1000000,1000000,1000000,1000000,1000000,100000 > 85 vector <int> replies(replies_, replies_+sizeof(replies_)/sizeof(*repli > 86 int _ = -1; > 87 END > 88 > 89 } > 90 // END CUT HERE
Added SRM/499-U/1B-U.cpp version [13e543b5a0b1db44]
> 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 <cstring> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 class WhiteSpaceEditing { public: > 23 int getMinimum(vector <int> lines) > 24 { > 25 const int N = lines.size(); > 26 const int V = *max_element(lines.begin(), lines.end()); > 27 vector<int> dp(V+1), dp_neo(V+1); > 28 for(int v=0; v<=V; ++v) > 29 dp[v] = abs(v - lines[N-1]); > 30 for(int i=N-2; i>=0; --i) > 31 { > 32 int best = INT_MAX; > 33 for(int v=lines[i]; v>=0; --v) { > 34 best = min(best, dp[v]); > 35 dp_neo[v] = abs(v - lines[i]) + best; > 36 } > 37 best = INT_MAX; > 38 for(int v=lines[i]; v<=V; ++v) { > 39 best = min(best, dp[v]); > 40 dp_neo[v] = abs(v - lines[i]) + best; > 41 } > 42 dp.swap(dp_neo); > 43 } > 44 return dp[0] + N-1; > 45 } > 46 }; > 47 > 48 // BEGIN CUT HERE > 49 #include <ctime> > 50 double start_time; string timer() > 51 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 52 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 53 { os << "{ "; > 54 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 55 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 56 void verify_case(const int& Expected, const int& Received) { > 57 bool ok = (Expected == Received); > 58 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 59 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 60 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 61 #define END verify_case(_, WhiteSpaceEditing().getMinimum(lines));} > 62 int main(){ > 63 > 64 CASE(0) > 65 int lines_[] = { 3, 2, 3 }; > 66 vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); > 67 int _ = 6; > 68 END > 69 CASE(1) > 70 int lines_[] = { 0 }; > 71 vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); > 72 int _ = 0; > 73 END > 74 CASE(2) > 75 int lines_[] = { 1, 2, 4 } > 76 ; > 77 vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); > 78 int _ = 6; > 79 END > 80 CASE(3) > 81 int lines_[] = { 250, 105, 155, 205, 350 } > 82 ; > 83 vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); > 84 int _ = 499; > 85 END > 86 CASE(4) > 87 int lines_[] = {0}; > 88 vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); > 89 int _ = 0; > 90 END > 91 CASE(5) > 92 int lines_[] = {1}; > 93 vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); > 94 int _ = 1; > 95 END > 96 CASE(5) > 97 int lines_[] = {10}; > 98 vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); > 99 int _ = 10; > 100 END > 101 CASE(5) > 102 int lines_[] = {10,10}; > 103 vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); > 104 int _ = 11; > 105 END > 106 CASE(5) > 107 int lines_[] = {1000000,1000000,1000000,1000000,1000000,1000000,1000000, > 108 vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); > 109 int _ = 1000049; > 110 END > 111 > 112 } > 113 // END CUT HERE
Added SRM/499-U/1C-U.cpp version [c23044dc81c5002a]
> 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 <cstring> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 template<typename V> > 23 class Graph > 24 { > 25 map<V, int> v2id_; > 26 vector<V> id2v_; > 27 public: > 28 vector< vector<int> > G; > 29 > 30 int vert( const V& t ) > 31 { > 32 if( !v2id_.count(t) ) { v2id_[t] = G.size(); id2v_.push_back(t); > 33 return v2id_[t]; > 34 } > 35 void edge( const V& s_, const V& t_ ) > 36 { > 37 int s=vert(s_), t=vert(t_); > 38 G[s].push_back(t); > 39 } > 40 const V& orig( int v ) > 41 { > 42 return id2v_[v]; > 43 } > 44 }; > 45 > 46 class StronglyConnectedComponent > 47 { > 48 public: > 49 StronglyConnectedComponent( const vector< vector<int> >& G ) > 50 : scc(), forest(), G(G), no(0), dfs_no(G.size()), dfs_lo(G.size( > 51 { > 52 for(int v=0; v<G.size(); ++v) > 53 dfs(v); > 54 } > 55 > 56 vector< vector<int> > scc; // scc[i] : the list of verts in the i-th > 57 vector< vector<int> > forest; // the forest structure over sccs > 58 > 59 private: > 60 const vector< vector<int> >& G; > 61 int no; > 62 vector<int> dfs_no; // Special: 0 : not visited yet > 63 vector<int> dfs_lo; // Special: INT_MAX : already classified into some s > 64 // rather use scc_id for that purpose (distinguishing assigned or not) > 65 vector<int> scc_id; > 66 vector<int> pending; > 67 > 68 void dfs(int v) > 69 { > 70 if( dfs_no[v] ) > 71 return; > 72 > 73 dfs_no[v] = dfs_lo[v] = ++no; // visit v > 74 for(int i=0; i<G[v].size(); ++i) // visit children > 75 { > 76 int u = G[v][i]; > 77 dfs( u ); > 78 if( !is_already_classified_in_some_scc(u) ) > 79 dfs_lo[v] = min( dfs_lo[v], dfs_lo[G[v][i]] ); > 80 } > 81 > 82 pending.push_back(v); > 83 if( dfs_no[v] == dfs_lo[v] ) { // found the representative of a > 84 // todo: pending -> dfs_lo:=INT_MAX > 85 scc.push_back(pending), pending.clear(); > 86 > 87 // construct scc-forest (if needed) > 88 scc_id[v] = scc.size()-1; > 89 set<int> children; > 90 for(int i=0; i<G[v].size(); ++i) > 91 if( dfs_lo[G[v][i]] != v ) > 92 children.insert( scc_id[dfs_lo[G[v][i]]] > 93 forest.push_back( vector<int>(children.begin(), children > 94 } > 95 } > 96 }; > 97 > 98 > 99 class ImpossibleGame { public: > 100 static LL C(LL n, LL k) { > 101 LL v = 1; > 102 for(int i=1; i<=k; ++i) > 103 v = v * (n+1-i) / i; > 104 return v; > 105 } > 106 static LL weight(LL a, LL b, LL c, LL d) { > 107 return C(a+b+c+d,a) * C(b+c+d,b) * C(c+d,c); > 108 } > 109 > 110 long long getMinimum(int k, vector <string> before, vector <string> afte > 111 { > 112 vector< pair< vector<int>, vector<int> > > dif; > 113 for(int i=0; i<after.size(); ++i) > 114 { > 115 vector<int> be(4), af(4); > 116 for(int j=0; j<before[i].size(); ++j) be[before[i][j]-'A > 117 for(int j=0; j< after[i].size(); ++j) af[ after[i][j]-'A > 118 dif.push_back( make_pair(be,af) ); > 119 } > 120 > 121 Graph< vector<int> > G; > 122 > 123 vector<int> v(4); > 124 for(v[0]=0; v[0]<=k; ++v[0]) > 125 for(v[1]=0; v[0]+v[1]<=k; ++v[1]) > 126 for(v[2]=0; v[0]+v[1]+v[2]<=k; ++v[2]) > 127 for(v[3]=0; v[0]+v[1]+v[2]+v[3]<=k; ++v[3]) > 128 { > 129 G.vert(v); > 130 for(int i=0; i<dif.size(); ++i) > 131 { > 132 bool dame = false; > 133 > 134 vector<int> u = v; > 135 for(int k=0; k<4; ++k) > 136 { > 137 if( (u[k]-=dif[i].first[k]) < 0 ) > 138 dame = true; > 139 u[k] += dif[i].second[k]; > 140 } > 141 if( !dame ) > 142 G.edge(v, u); > 143 } > 144 } > 145 > 146 StronglyConnectedComponent scc(G.G); > 147 return 0; > 148 } > 149 }; > 150 > 151 // BEGIN CUT HERE > 152 #include <ctime> > 153 double start_time; string timer() > 154 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 155 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 156 { os << "{ "; > 157 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 158 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 159 void verify_case(const long long& Expected, const long long& Received) { > 160 bool ok = (Expected == Received); > 161 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 162 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 163 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 164 #define END verify_case(_, ImpossibleGame().getMinimum(k, before, after));} > 165 int main(){ > 166 > 167 CASE(0) > 168 int k = 1; > 169 string before_[] = { "A" } > 170 ; > 171 vector <string> before(before_, before_+sizeof(before_)/sizeof(*before > 172 string after_[] = { "B" } > 173 ; > 174 vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_)); > 175 long long _ = 2LL; > 176 END > 177 CASE(1) > 178 int k = 2; > 179 string before_[] = { "A", "A", "D" } > 180 ; > 181 vector <string> before(before_, before_+sizeof(before_)/sizeof(*before > 182 string after_[] = { "B", "C", "D" } > 183 ; > 184 vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_)); > 185 long long _ = 5LL; > 186 END > 187 CASE(2) > 188 int k = 2; > 189 string before_[] = { "B", "C", "D" } > 190 ; > 191 vector <string> before(before_, before_+sizeof(before_)/sizeof(*before > 192 string after_[] = { "C", "D", "B" } > 193 ; > 194 vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_)); > 195 long long _ = 9LL; > 196 END > 197 CASE(3) > 198 int k = 6; > 199 string before_[] = { "AABBC", "AAAADA", "AAACA", "CABAA", "AAAAAA", "BAA > 200 ; > 201 vector <string> before(before_, before_+sizeof(before_)/sizeof(*before > 202 string after_[] = { "AACCB", "DAAABC", "AAAAD", "ABCBA", "AABAAA", "AACA > 203 ; > 204 vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_)); > 205 long long _ = 499LL; > 206 END > 207 /* > 208 CASE(4) > 209 int k = ; > 210 string before_[] = ; > 211 vector <string> before(before_, before_+sizeof(before_)/sizeof(*before > 212 string after_[] = ; > 213 vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_)); > 214 long long _ = LL; > 215 END > 216 CASE(5) > 217 int k = ; > 218 string before_[] = ; > 219 vector <string> before(before_, before_+sizeof(before_)/sizeof(*before > 220 string after_[] = ; > 221 vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_)); > 222 long long _ = LL; > 223 END > 224 */ > 225 } > 226 // END CUT HERE
Modified lib/numeric/modArith.cpp from [b348fa4dbce4653d] to [f45d60576bba9894].
2 //------------------------------------------------------------- 2 //------------------------------------------------------------- 3 // Modulo Arithmetics 3 // Modulo Arithmetics 4 // 4 // 5 // Verified by 5 // Verified by 6 // - TCO10 R3 LV3 6 // - TCO10 R3 LV3 7 //------------------------------------------------------------- 7 //------------------------------------------------------------- 8 8 9 static const int MODVAL = 1000000007; // op/ depends on primarity of the MODVAL | 9 static const int MODVAL = 1000000007; // must be prime for op/ 10 struct mint 10 struct mint 11 { 11 { 12 int val; 12 int val; 13 mint():val(0){} 13 mint():val(0){} 14 mint(int x):val(x%MODVAL) {} 14 mint(int x):val(x%MODVAL) {} 15 mint(LL x):val(x%MODVAL) {} 15 mint(LL x):val(x%MODVAL) {} 16 }; 16 }; 17 < 18 mint operator+(mint x, mint y) { return x.val+y.val; } 17 mint operator+(mint x, mint y) { return x.val+y.val; } 19 mint operator-(mint x, mint y) { return x.val-y.val+MODVAL; } 18 mint operator-(mint x, mint y) { return x.val-y.val+MODVAL; } 20 mint operator*(mint x, mint y) { return LL(x.val)*y.val; } 19 mint operator*(mint x, mint y) { return LL(x.val)*y.val; } 21 mint POW(mint x, int e) { 20 mint POW(mint x, int e) { 22 mint v = 1; 21 mint v = 1; 23 for(;e;x=x*x,e>>=1) 22 for(;e;x=x*x,e>>=1) 24 if(e&1) 23 if(e&1) 25 v=v*x; 24 v=v*x; 26 return v; 25 return v; 27 } 26 } 28 mint operator/(mint x, mint y) { return x * POW(y, MODVAL-2); } 27 mint operator/(mint x, mint y) { return x * POW(y, MODVAL-2); } 29 28 30 vector<mint> FAC_(1,1); 29 vector<mint> FAC_(1,1); 31 void FAC_INIT(int n) { for(int i=1; i<=n; ++i) FAC_.push_back( FAC_.back()*i ); | 30 void FAC_INIT(int n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*FAC_. 32 mint FAC(mint x) { return FAC_[x.val]; } 31 mint FAC(mint x) { return FAC_[x.val]; } 33 mint C(mint n, mint k) { return k.val<0 || n.val<k.val ? 0 : FAC(n) / (FAC(k) * 32 mint C(mint n, mint k) { return k.val<0 || n.val<k.val ? 0 : FAC(n) / (FAC(k) * 34 33 35 /* 34 /* 36 // MODVAL must be a prime!! 35 // MODVAL must be a prime!! 37 LL GSS(LL k, LL b, LL e) // k^b + k^b+1 + ... + k^e 36 LL GSS(LL k, LL b, LL e) // k^b + k^b+1 + ... + k^e 38 { 37 {
Deleted lib/numeric/modArithOld.cpp version [b669f317babaf285]
1 < 2 //------------------------------------------------------------- < 3 // Modulo Arithmetics < 4 // < 5 // Verified by < 6 // - SRM 397 Div1 LV2 < 7 // - SRM 428 Div1 LV2 < 8 // - CodeCraft 2010 CNTINT DRAW < 9 //------------------------------------------------------------- < 10 < 11 static const LL MODVAL = 1000000007; // must fit in 32-bits < 12 < 13 LL ADD(LL x, LL y) { return (x+y)%MODVAL; } < 14 LL SUB(LL x, LL y) { return (x-y+MODVAL)%MODVAL; } < 15 LL MUL(LL x, LL y) { return (x*y)%MODVAL; } < 16 LL POW(LL x, LL e) { < 17 LL v = 1; < 18 for(;e;x=MUL(x,x),e>>=1) < 19 if(e&1) < 20 v = MUL(v, x); < 21 return v; < 22 } < 23 < 24 // MODVAL must be a prime!! < 25 LL DIV(LL x, LL y) { return MUL(x, POW(y, MODVAL-2)); } < 26 < 27 // MODVAL must be a prime!! < 28 LL C(LL n, LL k) { < 29 LL v = 1; < 30 for(LL i=1; i<=k; ++i) < 31 v = DIV(MUL(v, n-i+1), i); < 32 return v; < 33 } < 34 < 35 // MODVAL must be a prime!! < 36 LL GSS(LL k, LL b, LL e) // k^b + k^b+1 + ... + k^e < 37 { < 38 if( b > e ) return 0; < 39 if( k <= 1 ) return k*(e-b+1); < 40 return DIV(SUB(POW(k, e+1), POW(k,b)), k-1); < 41 } < 42 < 43 < 44 < 45 < 46 LL Cpascal(LL n, LL k) < 47 { < 48 vector< vector<LL> > c(n+1, vector<LL>(k+1)); < 49 for(LL nn=1; nn<=n; ++nn) < 50 for(LL kk=0; kk<=min(nn,k); ++kk) < 51 c[nn][kk] = kk==0 || kk==nn ? 1 : ADD(c[nn-1][kk-1], c[n < 52 return c[n][k]; < 53 } < 54 < 55 vector< vector<LL> > MATMUL(vector< vector<LL> >& a, vector< vector<LL> >& b) < 56 { < 57 int N = a.size(); < 58 vector< vector<LL> > c(N, vector<LL>(N)); < 59 for(int i=0; i<N; ++i) < 60 for(int j=0; j<N; ++j) < 61 for(int k=0; k<N; ++k) < 62 c[i][j] = ADD(c[i][j], MUL(a[i][k],b[k][j])); < 63 return c; < 64 } < 65 < 66 // works for non-prime MODVAL < 67 LL GEO(LL x_, LL e) // x^0 + x^1 + ... + x^e-1 < 68 { < 69 vector< vector<LL> > v(2, vector<LL>(2)); < 70 vector< vector<LL> > x(2, vector<LL>(2)); < 71 v[0][0] = v[1][1] = 1; < 72 x[0][0] = x_; x[0][1] = 0; < 73 x[1][0] = 1 ; x[1][1] = 1; < 74 for(;e;x=MATMUL(x,x),e>>=1) < 75 if(e&1) < 76 v = MATMUL(v, x); < 77 return v[1][0]; < 78 } < 79 < 80 // works for non-prime MODVAL < 81 LL HYP(LL x_, LL e) // e x^0 + (e-1) x^1 + ... + 1 x^e-1 = GEO(x,1)+GEO(x,2)+... < 82 { < 83 vector< vector<LL> > v(3, vector<LL>(3)); < 84 vector< vector<LL> > x(3, vector<LL>(3)); < 85 v[0][0] = v[1][1] = v[2][2] = 1; < 86 x[0][0] = x_; x[0][1] = 0; x[0][2] = 0; < 87 x[1][0] = 1 ; x[1][1] = 1; x[1][2] = 0; < 88 x[2][0] = 0 ; x[2][1] = 1; x[2][2] = 1; < 89 e++; < 90 for(;e;x=MATMUL(x,x),e>>=1) < 91 if(e&1) < 92 v = MATMUL(v, x); < 93 return v[2][0]; < 94 } <