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 }