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 +}