Differences From Artifact [4e73ce5907de5c44]:
- File
lib/numeric/modArith.cpp
- 2012-08-06 15:25:10 - part of checkin [c81888b809] on branch trunk - 550 (user: kinaba) [annotate]
To Artifact [b6522f93bcade295]:
- File
lib/numeric/modArith.cpp
- 2012-09-02 11:59:33 - part of checkin [0ea7f42c5c] on branch trunk - 554 (user: kinaba) [annotate]
3 3 // Modulo Arithmetics
4 4 //
5 5 // Verified by
6 6 // - TCO10 R3 LV3
7 7 // - SRM 545 LV2
8 8 //-------------------------------------------------------------
9 9
10 -static const int MODVAL = 1000000007;
10 +static const unsigned MODVAL = 1000000007;
11 11 struct mint
12 12 {
13 - int val;
13 + unsigned val;
14 14 mint():val(0){}
15 - mint(int x):val(x%MODVAL) {}
16 - mint(size_t x):val(x%MODVAL) {}
17 - mint(LL x):val(x%MODVAL) {}
15 + mint(int x):val(x%MODVAL) {}
16 + mint(unsigned x):val(x%MODVAL) {}
17 + mint(LL x):val(x%MODVAL) {}
18 18 };
19 19 mint& operator+=(mint& x, mint y) { return x = x.val+y.val; }
20 20 mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; }
21 21 mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; }
22 -mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; }
23 -mint& operator/=(mint& x, mint y) { return x *= POW(y, MODVAL-2); }
24 22 mint operator+(mint x, mint y) { return x+=y; }
25 23 mint operator-(mint x, mint y) { return x-=y; }
26 24 mint operator*(mint x, mint y) { return x*=y; }
25 +
26 +mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; }
27 +mint& operator/=(mint& x, mint y) { return x *= POW(y, MODVAL-2); }
27 28 mint operator/(mint x, mint y) { return x/=y; }
29 +
30 +// nCk :: O(log MODVAL) time, O(n) space.
28 31 vector<mint> FAC_(1,1);
29 32 mint FAC(LL n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*FAC_.size() ); return FAC_[n]; }
30 33 mint C(LL n, LL k) { return k<0 || n<k ? 0 : FAC(n) / (FAC(k) * FAC(n-k)); }
31 -vector< vector<mint> > CP_; // Pascal's triangle: if O(1) nCk is needed.
34 +
35 +// nCk :: O(1) time, O(n^2) space.
36 +vector< vector<mint> > CP_;
32 37 mint C(LL n, LL k) {
33 38 while( CP_.size() <= n ) {
34 39 int nn = CP_.size();
35 40 CP_.push_back(vector<mint>(nn+1,1));
36 41 for(int kk=1; kk<nn; ++kk)
37 42 CP_[nn][kk] = CP_[nn-1][kk-1] + CP_[nn-1][kk];
38 43 }