Differences From Artifact [065fcd1fef379fbc]:
- File
lib/numeric/modArith.cpp
- 2012-09-08 04:27:24 - part of checkin [7d2fe88cb2] on branch trunk - Cleaned up matrix multication library. (user: kinaba) [annotate]
To Artifact [c76c99fca94dfde1]:
- File
lib/numeric/modArith.cpp
- 2013-08-02 01:01:11 - part of checkin [7f9fcaa19c] on branch trunk - Done. (user: kinaba) [annotate]
32 mint FAC(LL n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*FAC_.size() 32 mint FAC(LL n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*FAC_.size()
33 33
34 // nCk :: O(log MODVAL) time, O(n) space. 34 // nCk :: O(log MODVAL) time, O(n) space.
35 mint C(LL n, LL k) { return k<0 || n<k ? 0 : FAC(n) / (FAC(k) * FAC(n-k)); } 35 mint C(LL n, LL k) { return k<0 || n<k ? 0 : FAC(n) / (FAC(k) * FAC(n-k)); }
36 36
37 // nCk :: O(1) time, O(n^2) space. 37 // nCk :: O(1) time, O(n^2) space.
38 vector< vector<mint> > CP_; 38 vector< vector<mint> > CP_;
39 mint C(LL n, LL k) { | 39 mint C(int n, int k) {
40 while( CP_.size() <= n ) { 40 while( CP_.size() <= n ) {
41 int nn = CP_.size(); 41 int nn = CP_.size();
42 CP_.push_back(vector<mint>(nn+1,1)); 42 CP_.push_back(vector<mint>(nn+1,1));
43 for(int kk=1; kk<nn; ++kk) 43 for(int kk=1; kk<nn; ++kk)
44 CP_[nn][kk] = CP_[nn-1][kk-1] + CP_[nn-1][kk]; 44 CP_[nn][kk] = CP_[nn-1][kk-1] + CP_[nn-1][kk];
45 } 45 }
46 return k<0 || n<k ? 0 : CP_[n][k]; 46 return k<0 || n<k ? 0 : CP_[n][k];