• branch=trunk inherited from [9165bd3629]
• sym-trunk inherited from [9165bd3629]

Modified lib/numeric/modArith.cpp from [76c58f82b36b80e2] to [4dd19b13cd92c7f0].

     1      1   
     2      2   //-------------------------------------------------------------
     3      3   // Modulo Arithmetics
     4      4   //
     5      5   // Verified by
     6      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     11   struct mint
    11     12   {
    12     13    int val;
    13     14    mint():val(0){}
    14         - mint(int    x):val(x%MODVAL) {} // x>=0
    15         - mint(size_t x):val(x%MODVAL) {} // x>=0
    16         - mint(LL     x):val(x%MODVAL) {} // x>=0
           15  + mint(int    x):val(x%MODVAL) {}
           16  + mint(size_t x):val(x%MODVAL) {}
           17  + mint(LL     x):val(x%MODVAL) {}
    17     18   };
    18     19   mint& operator+=(mint& x, mint y) { return x = x.val+y.val; }
    19     20   mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; }
    20     21   mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; }
    21     22   mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; }
    22     23   mint& operator/=(mint& x, mint y) { return x *= POW(y, MODVAL-2); }
    23     24   mint operator+(mint x, mint y) { return x+=y; }
................................................................................

    24     25   mint operator-(mint x, mint y) { return x-=y; }
    25     26   mint operator*(mint x, mint y) { return x*=y; }
    26     27   mint operator/(mint x, mint y) { return x/=y; }
    27     28   vector<mint> FAC_(1,1);
    28     29   mint FAC(LL n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*FAC_.size() ); return FAC_[n]; }
    29     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_[nn-1][kk]:0) );
           40  + }
           41  + return k<0 || n<k ? 0 : CP_[n][k];
           42  +}
    31     43   
    32     44   
    33     45   
    34     46   /*
    35     47   // MODVAL must be a prime!!
    36     48   LL GSS(LL k, LL b, LL e) // k^b + k^b+1 + ... + k^e
    37     49   {