Differences From Artifact [b348fa4dbce4653d]:
- File
_lib/numeric/modArith.cpp
- 2011-02-23 09:21:16 - part of checkin [4fd800b3a8] on branch trunk - Copied from private svn repository. (user: kinaba) [annotate]
- File
lib/numeric/modArith.cpp
- 2011-02-23 11:18:09 - part of checkin [23dfcca431] on branch trunk - renamed _lib to lib (user: kinaba) [annotate]
To Artifact [f45d60576bba9894]:
- File
lib/numeric/modArith.cpp
- 2011-03-20 00:13:20 - part of checkin [2de557d8c0] on branch trunk - 499 (user: kinaba) [annotate]
2 2 //-------------------------------------------------------------
3 3 // Modulo Arithmetics
4 4 //
5 5 // Verified by
6 6 // - TCO10 R3 LV3
7 7 //-------------------------------------------------------------
8 8
9 -static const int MODVAL = 1000000007; // op/ depends on primarity of the MODVAL
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 14 mint(int x):val(x%MODVAL) {}
15 15 mint(LL x):val(x%MODVAL) {}
16 16 };
17 -
18 17 mint operator+(mint x, mint y) { return x.val+y.val; }
19 18 mint operator-(mint x, mint y) { return x.val-y.val+MODVAL; }
20 19 mint operator*(mint x, mint y) { return LL(x.val)*y.val; }
21 20 mint POW(mint x, int e) {
22 21 mint v = 1;
23 22 for(;e;x=x*x,e>>=1)
24 23 if(e&1)
25 24 v=v*x;
26 25 return v;
27 26 }
28 27 mint operator/(mint x, mint y) { return x * POW(y, MODVAL-2); }
29 28
30 29 vector<mint> FAC_(1,1);
31 -void FAC_INIT(int n) { for(int i=1; i<=n; ++i) FAC_.push_back( FAC_.back()*i ); }
30 +void FAC_INIT(int n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*FAC_.size() ); }
32 31 mint FAC(mint x) { return FAC_[x.val]; }
33 32 mint C(mint n, mint k) { return k.val<0 || n.val<k.val ? 0 : FAC(n) / (FAC(k) * FAC(n-k)); }
34 33
35 34 /*
36 35 // MODVAL must be a prime!!
37 36 LL GSS(LL k, LL b, LL e) // k^b + k^b+1 + ... + k^e
38 37 {