setfunc/count_surjection.hpp

• View this file on GitHub
• Last update: 2022-04-16 19:49:52+09:00
• Include: #include "setfunc/count_surjection.hpp"

Verified with

• test/4_aoj/DPL_5_C.test.cpp

Code

template<typename mint>
mint count_surjection(ll n, ll m) {
  if (n < m) return 0;
  mint res = 0;
  FOR(i, m + 1) {
    mint sgn = ((m - i) & 1 ? -1 : 1);
    res += mint(i).pow(n) * C<mint>(m, i) * sgn;
  }
  return res;
}

#line 1 "setfunc/count_surjection.hpp"
template<typename mint>
mint count_surjection(ll n, ll m) {
  if (n < m) return 0;
  mint res = 0;
  FOR(i, m + 1) {
    mint sgn = ((m - i) & 1 ? -1 : 1);
    res += mint(i).pow(n) * C<mint>(m, i) * sgn;
  }
  return res;
}

Back to top page