Differences From Artifact [f45d60576bba9894]:
- File
lib/numeric/modArith.cpp
- 2011-03-20 00:13:20 - part of checkin [2de557d8c0] on branch trunk - 499 (user: kinaba) [annotate]
To 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]
7 7 //-------------------------------------------------------------
8 8
9 9 static const int MODVAL = 1000000007; // must be prime for op/
10 10 struct mint
11 11 {
12 12 int val;
13 13 mint():val(0){}
14 - mint(int x):val(x%MODVAL) {}
15 - mint(LL x):val(x%MODVAL) {}
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
16 17 };
17 -mint operator+(mint x, mint y) { return x.val+y.val; }
18 -mint operator-(mint x, mint y) { return x.val-y.val+MODVAL; }
19 -mint operator*(mint x, mint y) { return LL(x.val)*y.val; }
20 -mint POW(mint x, int e) {
21 - mint v = 1;
22 - for(;e;x=x*x,e>>=1)
23 - if(e&1)
24 - v=v*x;
25 - return v;
26 -}
27 -mint operator/(mint x, mint y) { return x * POW(y, MODVAL-2); }
18 +mint& operator+=(mint& x, mint y) { return x = x.val+y.val; }
19 +mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; }
20 +mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; }
21 +mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; }
22 +mint& operator/=(mint& x, mint y) { return x *= POW(y, MODVAL-2); }
23 +mint operator+(mint x, mint y) { return x+=y; }
24 +mint operator-(mint x, mint y) { return x-=y; }
25 +mint operator*(mint x, mint y) { return x*=y; }
26 +mint operator/(mint x, mint y) { return x/=y; }
27 +vector<mint> FAC_(1,1);
28 +mint FAC(LL n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*FAC_.size() ); return FAC_[n]; }
29 +mint C(LL n, LL k) { return k<0 || n<k ? 0 : FAC(n) / (FAC(k) * FAC(n-k)); }
30 +
28 31
29 -vector<mint> FAC_(1,1);
30 -void FAC_INIT(int n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*FAC_.size() ); }
31 -mint FAC(mint x) { return FAC_[x.val]; }
32 -mint C(mint n, mint k) { return k.val<0 || n.val<k.val ? 0 : FAC(n) / (FAC(k) * FAC(n-k)); }
32 +
33 33
34 34 /*
35 35 // MODVAL must be a prime!!
36 36 LL GSS(LL k, LL b, LL e) // k^b + k^b+1 + ... + k^e
37 37 {
38 38 if( b > e ) return 0;
39 39 if( k <= 1 ) return k*(e-b+1);