This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ei1333/library
#include "math/combinatorics/factorial.hpp"
#include "sample-point-shift.hpp" /** * @brief Factorial(階乗) */ template< typename Mint, typename F > Mint factorial(int64_t n, const F& multiply) { if(n <= 1) return 1; if(n >= Mint::get_mod()) return 0; int64_t v = 1; while(v * v < n) v *= 2; Mint iv = Mint(1) / v; vector< Mint > G{1, v + 1}; for(int64_t d = 1; d != v; d <<= 1) { vector< Mint > G1 = sample_point_shift(G, Mint(d) * iv, multiply); vector< Mint > G2 = sample_point_shift(G, Mint(d * v + v) * iv, multiply); vector< Mint > G3 = sample_point_shift(G, Mint(d * v + d + v) * iv, multiply); for(int i = 0; i <= d; i++) G[i] *= G1[i], G2[i] *= G3[i]; copy(begin(G2), end(G2) - 1, back_inserter(G)); } Mint res = 1; int64_t i = 0; while(i + v <= n) res *= G[i / v], i += v; while(i < n) res *= ++i; return res; }
#line 1 "math/combinatorics/enumeration.hpp" /** * @brief Enumeration(組み合わせ) */ template< typename T > struct Enumeration { private: static vector< T > _fact, _finv, _inv; inline static void expand(size_t sz) { if(_fact.size() < sz + 1) { int pre_sz = max(1, (int) _fact.size()); _fact.resize(sz + 1, T(1)); _finv.resize(sz + 1, T(1)); _inv.resize(sz + 1, T(1)); for(int i = pre_sz; i <= (int) sz; i++) { _fact[i] = _fact[i - 1] * T(i); } _finv[sz] = T(1) / _fact[sz]; for(int i = (int) sz - 1; i >= pre_sz; i--) { _finv[i] = _finv[i + 1] * T(i + 1); } for(int i = pre_sz; i <= (int) sz; i++) { _inv[i] = _finv[i] * _fact[i - 1]; } } } public: explicit Enumeration(size_t sz = 0) { expand(sz); } static inline T fact(int k) { expand(k); return _fact[k]; } static inline T finv(int k) { expand(k); return _finv[k]; } static inline T inv(int k) { expand(k); return _inv[k]; } static T P(int n, int r) { if(r < 0 || n < r) return 0; return fact(n) * finv(n - r); } static T C(int p, int q) { if(q < 0 || p < q) return 0; return fact(p) * finv(q) * finv(p - q); } static T H(int n, int r) { if(n < 0 || r < 0) return 0; return r == 0 ? 1 : C(n + r - 1, r); } }; template< typename T > vector< T > Enumeration< T >::_fact = vector< T >(); template< typename T > vector< T > Enumeration< T >::_finv = vector< T >(); template< typename T > vector< T > Enumeration< T >::_inv = vector< T >(); #line 2 "math/combinatorics/sample-point-shift.hpp" /** * @brief Sample Point Shift(標本点シフト) */ template< typename Mint, typename F > vector< Mint > sample_point_shift(const vector< Mint > &ys, const Mint &m, const F &multiply) { Enumeration< Mint > comb; int d = (int) ys.size() - 1; vector< Mint > f(d + 1), g(d * 2 + 1); for(int i = 0; i <= d; i++) { f[i] = ys[i] * comb.finv(i) * comb.finv(d - i); if((d - i) & 1) f[i] = -f[i]; } for(int i = 0; i <= 2 * d; i++) { g[i] = Mint(1) / (m - d + i); } auto h = multiply(f, g); Mint coef = 1; for(int i = 0; i <= d; i++) { coef *= (m - d + i); } for(int i = 0; i <= d; i++) { h[i + d] *= coef; coef *= (m + i + 1) * g[i]; } return vector< Mint >{begin(h) + d, begin(h) + 2 * d + 1}; } #line 2 "math/combinatorics/factorial.hpp" /** * @brief Factorial(階乗) */ template< typename Mint, typename F > Mint factorial(int64_t n, const F& multiply) { if(n <= 1) return 1; if(n >= Mint::get_mod()) return 0; int64_t v = 1; while(v * v < n) v *= 2; Mint iv = Mint(1) / v; vector< Mint > G{1, v + 1}; for(int64_t d = 1; d != v; d <<= 1) { vector< Mint > G1 = sample_point_shift(G, Mint(d) * iv, multiply); vector< Mint > G2 = sample_point_shift(G, Mint(d * v + v) * iv, multiply); vector< Mint > G3 = sample_point_shift(G, Mint(d * v + d + v) * iv, multiply); for(int i = 0; i <= d; i++) G[i] *= G1[i], G2[i] *= G3[i]; copy(begin(G2), end(G2) - 1, back_inserter(G)); } Mint res = 1; int64_t i = 0; while(i + v <= n) res *= G[i / v], i += v; while(i < n) res *= ++i; return res; }