23dfcca431 2011-02-23 kinaba: 23dfcca431 2011-02-23 kinaba: //------------------------------------------------------------- 23dfcca431 2011-02-23 kinaba: // Modulo Arithmetics 23dfcca431 2011-02-23 kinaba: // 23dfcca431 2011-02-23 kinaba: // Verified by 23dfcca431 2011-02-23 kinaba: // - TCO10 R3 LV3 7d2fe88cb2 2012-09-08 kinaba: // - SRM 545 Div1 LV2 7d2fe88cb2 2012-09-08 kinaba: // - SRM 554 Div1 LV3 23dfcca431 2011-02-23 kinaba: //------------------------------------------------------------- 23dfcca431 2011-02-23 kinaba: 0ea7f42c5c 2012-09-02 kinaba: static const unsigned MODVAL = 1000000007; 23dfcca431 2011-02-23 kinaba: struct mint 23dfcca431 2011-02-23 kinaba: { 0ea7f42c5c 2012-09-02 kinaba: unsigned val; 23dfcca431 2011-02-23 kinaba: mint():val(0){} 0ea7f42c5c 2012-09-02 kinaba: mint(int x):val(x%MODVAL) {} 0ea7f42c5c 2012-09-02 kinaba: mint(unsigned x):val(x%MODVAL) {} 0ea7f42c5c 2012-09-02 kinaba: mint(LL x):val(x%MODVAL) {} 23dfcca431 2011-02-23 kinaba: }; 068d2337c1 2011-09-18 kinaba: mint& operator+=(mint& x, mint y) { return x = x.val+y.val; } 068d2337c1 2011-09-18 kinaba: mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; } 068d2337c1 2011-09-18 kinaba: mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; } 068d2337c1 2011-09-18 kinaba: mint operator+(mint x, mint y) { return x+=y; } 068d2337c1 2011-09-18 kinaba: mint operator-(mint x, mint y) { return x-=y; } 068d2337c1 2011-09-18 kinaba: mint operator*(mint x, mint y) { return x*=y; } 0ea7f42c5c 2012-09-02 kinaba: 0ea7f42c5c 2012-09-02 kinaba: mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; } 0ea7f42c5c 2012-09-02 kinaba: mint& operator/=(mint& x, mint y) { return x *= POW(y, MODVAL-2); } 068d2337c1 2011-09-18 kinaba: mint operator/(mint x, mint y) { return x/=y; } 0ea7f42c5c 2012-09-02 kinaba: 23dfcca431 2011-02-23 kinaba: vector<mint> FAC_(1,1); cc4202a4a6 2015-08-22 kinaba: mint FAC(LL n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*LL(FAC_.size()) ); return FAC_[n]; } 7d2fe88cb2 2012-09-08 kinaba: 7d2fe88cb2 2012-09-08 kinaba: // nCk :: O(log MODVAL) time, O(n) space. 068d2337c1 2011-09-18 kinaba: mint C(LL n, LL k) { return k<0 || n<k ? 0 : FAC(n) / (FAC(k) * FAC(n-k)); } 0ea7f42c5c 2012-09-02 kinaba: 0ea7f42c5c 2012-09-02 kinaba: // nCk :: O(1) time, O(n^2) space. 0ea7f42c5c 2012-09-02 kinaba: vector< vector<mint> > CP_; 7f9fcaa19c 2013-08-02 kinaba: mint C(int n, int k) { 4318dd2827 2012-06-07 kinaba: while( CP_.size() <= n ) { 4318dd2827 2012-06-07 kinaba: int nn = CP_.size(); 4318dd2827 2012-06-07 kinaba: CP_.push_back(vector<mint>(nn+1,1)); 4318dd2827 2012-06-07 kinaba: for(int kk=1; kk<nn; ++kk) 4318dd2827 2012-06-07 kinaba: CP_[nn][kk] = CP_[nn-1][kk-1] + CP_[nn-1][kk]; 16685c1758 2012-06-07 kinaba: } 16685c1758 2012-06-07 kinaba: return k<0 || n<k ? 0 : CP_[n][k]; 23dfcca431 2011-02-23 kinaba: } 23dfcca431 2011-02-23 kinaba: 7d2fe88cb2 2012-09-08 kinaba: // O(log MODVAL), MODVAL must be prime: k^b + k^b+1 + ... + k^e 7d2fe88cb2 2012-09-08 kinaba: mint GSS(mint k, LL b, LL e) 23dfcca431 2011-02-23 kinaba: { 7d2fe88cb2 2012-09-08 kinaba: if( b > e ) return 0; 7d2fe88cb2 2012-09-08 kinaba: if( k.val <= 1 ) return k*(e-b+1); 7d2fe88cb2 2012-09-08 kinaba: return (POW(k, e+1) - POW(k,b)) / (k-1); efadb95ceb 2019-07-06 kinaba: } efadb95ceb 2019-07-06 kinaba: efadb95ceb 2019-07-06 kinaba: // https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind efadb95ceb 2019-07-06 kinaba: // Number of ways to split |n| labelled objects to exactly |k| unlabbled sets. efadb95ceb 2019-07-06 kinaba: // * If we drop "exactly", the answer was k^n efadb95ceb 2019-07-06 kinaba: // * If we split to "labeled" sets, the answer will be S(n,k)*k! efadb95ceb 2019-07-06 kinaba: // * If unlabeled/unlabeld bar-and-ball-arranging argument. efadb95ceb 2019-07-06 kinaba: vector< vector<mint> > SP_; efadb95ceb 2019-07-06 kinaba: mint S(int n, int k) { efadb95ceb 2019-07-06 kinaba: while (SP_.size() <= n) { efadb95ceb 2019-07-06 kinaba: int nn = SP_.size(); efadb95ceb 2019-07-06 kinaba: SP_.push_back(vector<mint>(nn + 1, 1)); efadb95ceb 2019-07-06 kinaba: for (int kk = 2; kk<nn; ++kk) efadb95ceb 2019-07-06 kinaba: SP_[nn][kk] = SP_[nn - 1][kk - 1] + kk*SP_[nn - 1][kk]; efadb95ceb 2019-07-06 kinaba: } efadb95ceb 2019-07-06 kinaba: return k<=0 || n<k ? 0 : SP_[n][k]; c81888b809 2012-08-06 kinaba: }