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 // - SRM 545 LV2 8 //------------------------------------------------------------- 8 //------------------------------------------------------------- 9 9 10 static const int MODVAL = 1000000007; | 10 static const unsigned MODVAL = 1000000007; 11 struct mint 11 struct mint 12 { 12 { 13 int val; | 13 unsigned val; 14 mint():val(0){} 14 mint():val(0){} 15 mint(int x):val(x%MODVAL) {} | 15 mint(int x):val(x%MODVAL) {} 16 mint(size_t x):val(x%MODVAL) {} | 16 mint(unsigned x):val(x%MODVAL) {} 17 mint(LL x):val(x%MODVAL) {} | 17 mint(LL x):val(x%MODVAL) {} 18 }; 18 }; 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; } 20 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; } 21 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; } 22 mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; } < 23 mint& operator/=(mint& x, mint y) { return x *= POW(y, MODVAL-2); } < 24 mint operator+(mint x, mint y) { return x+=y; } 22 mint operator+(mint x, mint y) { return x+=y; } 25 mint operator-(mint x, mint y) { return x-=y; } 23 mint operator-(mint x, mint y) { return x-=y; } 26 mint operator*(mint x, mint y) { return x*=y; } 24 mint operator*(mint x, mint y) { return x*=y; } > 25 > 26 mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; } > 27 mint& operator/=(mint& x, mint y) { return x *= POW(y, MODVAL-2); } 27 mint operator/(mint x, mint y) { return x/=y; } 28 mint operator/(mint x, mint y) { return x/=y; } > 29 > 30 // nCk :: O(log MODVAL) time, O(n) space. 28 vector<mint> FAC_(1,1); 31 vector<mint> FAC_(1,1); 29 mint FAC(LL n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*FAC_.size() 32 mint FAC(LL n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*FAC_.size() 30 mint C(LL n, LL k) { return k<0 || n<k ? 0 : FAC(n) / (FAC(k) * FAC(n-k)); } 33 mint C(LL n, LL k) { return k<0 || n<k ? 0 : FAC(n) / (FAC(k) * FAC(n-k)); } > 34 > 35 // nCk :: O(1) time, O(n^2) space. 31 vector< vector<mint> > CP_; // Pascal's triangle: if O(1) nCk is needed. | 36 vector< vector<mint> > CP_; 32 mint C(LL n, LL k) { 37 mint C(LL n, LL k) { 33 while( CP_.size() <= n ) { 38 while( CP_.size() <= n ) { 34 int nn = CP_.size(); 39 int nn = CP_.size(); 35 CP_.push_back(vector<mint>(nn+1,1)); 40 CP_.push_back(vector<mint>(nn+1,1)); 36 for(int kk=1; kk<nn; ++kk) 41 for(int kk=1; kk<nn; ++kk) 37 CP_[nn][kk] = CP_[nn-1][kk-1] + CP_[nn-1][kk]; 42 CP_[nn][kk] = CP_[nn-1][kk-1] + CP_[nn-1][kk]; 38 } 43 }