Overview
| SHA1 Hash: | 16685c17580c800fb8aa23fa6f1c9327494ba4d4 |
|---|---|
| Date: | 2012-06-07 17:46:35 |
| User: | kinaba |
| Comment: | Pascal's triangle. |
| Timelines: | family | ancestors | descendants | both | trunk |
| Downloads: | Tarball | ZIP archive |
| Other Links: | files | file ages | manifest |
Tags And Properties
- branch=trunk inherited from [9165bd3629]
- sym-trunk inherited from [9165bd3629]
Changes
Modified lib/numeric/modArith.cpp from [76c58f82b36b80e2] to [4dd19b13cd92c7f0].
1 1 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 // - SRM 545 LV2 7 //------------------------------------------------------------- 8 //------------------------------------------------------------- 8 9 9 static const int MODVAL = 1000000007; // must be prime for op/ | 10 static const int MODVAL = 1000000007; 10 struct mint 11 struct mint 11 { 12 { 12 int val; 13 int val; 13 mint():val(0){} 14 mint():val(0){} 14 mint(int x):val(x%MODVAL) {} // x>=0 | 15 mint(int x):val(x%MODVAL) {} 15 mint(size_t x):val(x%MODVAL) {} // x>=0 | 16 mint(size_t x):val(x%MODVAL) {} 16 mint(LL x):val(x%MODVAL) {} // x>=0 | 17 mint(LL x):val(x%MODVAL) {} 17 }; 18 }; 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; } 19 mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; } 20 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& 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 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 *= POW(y, MODVAL-2); } 23 mint operator+(mint x, mint y) { return x+=y; } 24 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; } 25 mint operator*(mint x, mint y) { return x*=y; } 26 mint operator*(mint x, mint y) { return x*=y; } 26 mint operator/(mint x, mint y) { return x/=y; } 27 mint operator/(mint x, mint y) { return x/=y; } 27 vector<mint> FAC_(1,1); 28 vector<mint> FAC_(1,1); 28 mint FAC(LL n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*FAC_.size() 29 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)); } 30 mint C(LL n, LL k) { return k<0 || n<k ? 0 : FAC(n) / (FAC(k) * FAC(n-k)); } 30 31 > 32 // Pascal's triangle: if O(1) nCk is needed. > 33 vector< vector<mint> > CP_(2001); > 34 mint C(LL n, LL k) { > 35 if(CP_[0].empty()) { > 36 CP_[0].push_back(1); > 37 for(int nn=1; nn<CP_.size(); ++nn) > 38 for(int kk=0; kk<=nn; ++kk) > 39 CP_[nn].push_back( (kk?CP_[nn-1][kk-1]:0) + (kk<nn?CP_[n > 40 } > 41 return k<0 || n<k ? 0 : CP_[n][k]; > 42 } 31 43 32 44 33 45 34 /* 46 /* 35 // MODVAL must be a prime!! 47 // MODVAL must be a prime!! 36 LL GSS(LL k, LL b, LL e) // k^b + k^b+1 + ... + k^e 48 LL GSS(LL k, LL b, LL e) // k^b + k^b+1 + ... + k^e 37 { 49 {