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

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

    49     49   // O(log MODVAL), MODVAL must be prime: k^b + k^b+1 + ... + k^e
    50     50   mint GSS(mint k, LL b, LL e)
    51     51   {
    52     52    if( b > e ) return 0;
    53     53    if( k.val <= 1 ) return k*(e-b+1);
    54     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  +}