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

Modified lib/numeric/modArith.cpp from [d49aef5cfc6580a0] to [a7ea12621faece16].

   49  // O(log MODVAL), MODVAL must be prime: k^b + k^b+1 + ... + k^e                       49  // O(log MODVAL), MODVAL must be prime: k^b + k^b+1 + ... + k^e
   50  mint GSS(mint k, LL b, LL e)                                                          50  mint GSS(mint k, LL b, LL e)
   51  {                                                                                     51  {
   52          if( b > e ) return 0;                                                         52          if( b > e ) return 0;
   53          if( k.val <= 1 ) return k*(e-b+1);                                            53          if( k.val <= 1 ) return k*(e-b+1);
   54          return (POW(k, e+1) - POW(k,b)) / (k-1);                                      54          return (POW(k, e+1) - POW(k,b)) / (k-1);
   55  }                                                                                     55  }
                                                                                        >    56  
                                                                                        >    57  // https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind
                                                                                        >    58  // Number of ways to split |n| labelled objects to exactly |k| unlabbled sets.
                                                                                        >    59  //    * If we drop "exactly", the answer was k^n
                                                                                        >    60  //    * If we split to "labeled" sets, the answer will be S(n,k)*k!
                                                                                        >    61  //    * If unlabeled/unlabeld bar-and-ball-arranging argument.
                                                                                        >    62  vector< vector<mint> > SP_;
                                                                                        >    63  mint S(int n, int k) {
                                                                                        >    64          while (SP_.size() <= n) {
                                                                                        >    65                  int nn = SP_.size();
                                                                                        >    66                  SP_.push_back(vector<mint>(nn + 1, 1));
                                                                                        >    67                  for (int kk = 2; kk<nn; ++kk)
                                                                                        >    68                          SP_[nn][kk] = SP_[nn - 1][kk - 1] + kk*SP_[nn - 1][kk];
                                                                                        >    69          }
                                                                                        >    70          return k<=0 || n<k ? 0 : SP_[n][k];
                                                                                        >    71  }