Differences From Artifact [4dd19b13cd92c7f0]:
- File
lib/numeric/modArith.cpp
- 2012-06-07 17:46:35 - part of checkin [16685c1758] on branch trunk - Pascal's triangle. (user: kinaba) [annotate]
To Artifact [e5662c451b84a185]:
- File
lib/numeric/modArith.cpp
- 2012-06-07 18:00:23 - part of checkin [4318dd2827] on branch trunk - Cleaner interface. (user: kinaba) [annotate]
24 24 mint operator+(mint x, mint y) { return x+=y; }
25 25 mint operator-(mint x, mint y) { return x-=y; }
26 26 mint operator*(mint x, mint y) { return x*=y; }
27 27 mint operator/(mint x, mint y) { return x/=y; }
28 28 vector<mint> FAC_(1,1);
29 29 mint FAC(LL n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*FAC_.size() ); return FAC_[n]; }
30 30 mint C(LL n, LL k) { return k<0 || n<k ? 0 : FAC(n) / (FAC(k) * FAC(n-k)); }
31 -
32 -// Pascal's triangle: if O(1) nCk is needed.
33 -vector< vector<mint> > CP_(2001);
31 +vector< vector<mint> > CP_; // Pascal's triangle: if O(1) nCk is needed.
34 32 mint C(LL n, LL k) {
35 - if(CP_[0].empty()) {
36 - CP_[0].push_back(1);
37 - for(int nn=1; nn<CP_.size(); ++nn)
38 - for(int kk=0; kk<=nn; ++kk)
39 - CP_[nn].push_back( (kk?CP_[nn-1][kk-1]:0) + (kk<nn?CP_[nn-1][kk]:0) );
33 + while( CP_.size() <= n ) {
34 + int nn = CP_.size();
35 + CP_.push_back(vector<mint>(nn+1,1));
36 + for(int kk=1; kk<nn; ++kk)
37 + CP_[nn][kk] = CP_[nn-1][kk-1] + CP_[nn-1][kk];
40 38 }
41 39 return k<0 || n<k ? 0 : CP_[n][k];
42 40 }
43 -
44 -
45 41
46 42 /*
47 43 // MODVAL must be a prime!!
48 44 LL GSS(LL k, LL b, LL e) // k^b + k^b+1 + ... + k^e
49 45 {
50 46 if( b > e ) return 0;
51 47 if( k <= 1 ) return k*(e-b+1);