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 // Modulo Arithmetics 3 // Modulo Arithmetics
4 // 4 //
5 // Verified by 5 // Verified by
6 // - TCO10 R3 LV3 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 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) {} 14 mint(int x):val(x%MODVAL) {}
15 mint(LL x):val(x%MODVAL) {} 15 mint(LL x):val(x%MODVAL) {}
16 }; 16 };
17 <
18 mint operator+(mint x, mint y) { return x.val+y.val; } 17 mint operator+(mint x, mint y) { return x.val+y.val; }
19 mint operator-(mint x, mint y) { return x.val-y.val+MODVAL; } 18 mint operator-(mint x, mint y) { return x.val-y.val+MODVAL; }
20 mint operator*(mint x, mint y) { return LL(x.val)*y.val; } 19 mint operator*(mint x, mint y) { return LL(x.val)*y.val; }
21 mint POW(mint x, int e) { 20 mint POW(mint x, int e) {
22 mint v = 1; 21 mint v = 1;
23 for(;e;x=x*x,e>>=1) 22 for(;e;x=x*x,e>>=1)
24 if(e&1) 23 if(e&1)
25 v=v*x; 24 v=v*x;
26 return v; 25 return v;
27 } 26 }
28 mint operator/(mint x, mint y) { return x * POW(y, MODVAL-2); } 27 mint operator/(mint x, mint y) { return x * POW(y, MODVAL-2); }
29 28
30 vector<mint> FAC_(1,1); 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_.
32 mint FAC(mint x) { return FAC_[x.val]; } 31 mint FAC(mint x) { return FAC_[x.val]; }
33 mint C(mint n, mint k) { return k.val<0 || n.val<k.val ? 0 : FAC(n) / (FAC(k) * 32 mint C(mint n, mint k) { return k.val<0 || n.val<k.val ? 0 : FAC(n) / (FAC(k) *
34 33
35 /* 34 /*
36 // MODVAL must be a prime!! 35 // MODVAL must be a prime!!
37 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
38 { 37 {