Differences From Artifact [76c58f82b36b80e2]:
- File
lib/numeric/modArith.cpp
- 2011-09-18 02:59:23 - part of checkin [068d2337c1] on branch trunk - mod arith library revised. (user: kinaba) [annotate]
To 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]
1 1
2 2 //-------------------------------------------------------------
3 3 // Modulo Arithmetics
4 4 //
5 5 // Verified by
6 6 // - TCO10 R3 LV3
7 +// - SRM 545 LV2
7 8 //-------------------------------------------------------------
8 9
9 -static const int MODVAL = 1000000007; // must be prime for op/
10 +static const int MODVAL = 1000000007;
10 11 struct mint
11 12 {
12 13 int val;
13 14 mint():val(0){}
14 - mint(int x):val(x%MODVAL) {} // x>=0
15 - mint(size_t x):val(x%MODVAL) {} // x>=0
16 - mint(LL x):val(x%MODVAL) {} // x>=0
15 + mint(int x):val(x%MODVAL) {}
16 + mint(size_t x):val(x%MODVAL) {}
17 + mint(LL x):val(x%MODVAL) {}
17 18 };
18 19 mint& operator+=(mint& x, mint y) { return x = x.val+y.val; }
19 20 mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; }
20 21 mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; }
21 22 mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; }
22 23 mint& operator/=(mint& x, mint y) { return x *= POW(y, MODVAL-2); }
23 24 mint operator+(mint x, mint y) { return x+=y; }
................................................................................
24 25 mint operator-(mint x, mint y) { return x-=y; }
25 26 mint operator*(mint x, mint y) { return x*=y; }
26 27 mint operator/(mint x, mint y) { return x/=y; }
27 28 vector<mint> FAC_(1,1);
28 29 mint FAC(LL n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*FAC_.size() ); return FAC_[n]; }
29 30 mint C(LL n, LL k) { return k<0 || n<k ? 0 : FAC(n) / (FAC(k) * FAC(n-k)); }
30 31
32 +// Pascal's triangle: if O(1) nCk is needed.
33 +vector< vector<mint> > CP_(2001);
34 +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) );
40 + }
41 + return k<0 || n<k ? 0 : CP_[n][k];
42 +}
31 43
32 44
33 45
34 46 /*
35 47 // MODVAL must be a prime!!
36 48 LL GSS(LL k, LL b, LL e) // k^b + k^b+1 + ... + k^e
37 49 {