Diff
Not logged in

Differences From Artifact [b348fa4dbce4653d]:

To Artifact [f45d60576bba9894]:


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 {