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 static const int MODVAL = 1000000007; // must be prime for op/ 9 static const int MODVAL = 1000000007; // must be prime for op/
10 struct mint 10 struct mint
11 { 11 {
12 int val; 12 int val;
13 mint():val(0){} 13 mint():val(0){}
> 14 mint(int x):val(x%MODVAL) {} // x>=0
14 mint(int x):val(x%MODVAL) {} | 15 mint(size_t x):val(x%MODVAL) {} // x>=0
15 mint(LL x):val(x%MODVAL) {} | 16 mint(LL x):val(x%MODVAL) {} // x>=0
16 }; 17 };
> 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); }
17 mint operator+(mint x, mint y) { return x.val+y.val; } | 23 mint operator+(mint x, mint y) { return x+=y; }
18 mint operator-(mint x, mint y) { return x.val-y.val+MODVAL; } | 24 mint operator-(mint x, mint y) { return x-=y; }
19 mint operator*(mint x, mint y) { return LL(x.val)*y.val; } | 25 mint operator*(mint x, mint y) { return x*=y; }
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 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()
> 29 mint C(LL n, LL k) { return k<0 || n<k ? 0 : FAC(n) / (FAC(k) * FAC(n-k)); }
26 } | 30
27 mint operator/(mint x, mint y) { return x * POW(y, MODVAL-2); } <
28 31
29 vector<mint> FAC_(1,1); <
30 void FAC_INIT(int n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*FAC_. <
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) * <
> 32
33 33
34 /* 34 /*
35 // MODVAL must be a prime!! 35 // MODVAL must be a prime!!
36 LL GSS(LL k, LL b, LL e) // k^b + k^b+1 + ... + k^e 36 LL GSS(LL k, LL b, LL e) // k^b + k^b+1 + ... + k^e
37 { 37 {
38 if( b > e ) return 0; 38 if( b > e ) return 0;
39 if( k <= 1 ) return k*(e-b+1); 39 if( k <= 1 ) return k*(e-b+1);