This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#define PROBLEM "https://atcoder.jp/contests/abc240/tasks/abc240_g" #include <iostream> #include <atcoder/modint> using mint = atcoder::modint998244353; #include "library/math/util.hpp" int main() { int n, x, y, z; std::cin >> n >> x >> y >> z; suisen::factorial<mint> fac(n); mint ans = 0; for (int i = 0; i <= n; ++i) { int j = i - z; ans += fac.binom(n, i) * fac.binom(n - i, j) * suisen::random_walk_2d<mint>(n - i - j, x, y); } std::cout << ans.val() << std::endl; return 0; }
#line 1 "test/src/math/util/abc240_g.test.cpp" #define PROBLEM "https://atcoder.jp/contests/abc240/tasks/abc240_g" #include <iostream> #include <atcoder/modint> using mint = atcoder::modint998244353; #line 1 "library/math/util.hpp" #line 1 "library/math/factorial.hpp" #include <cassert> #include <vector> namespace suisen { template <typename T, typename U = T> struct factorial { factorial() = default; factorial(int n) { ensure(n); } static void ensure(const int n) { int sz = _fac.size(); if (n + 1 <= sz) return; int new_size = std::max(n + 1, sz * 2); _fac.resize(new_size), _fac_inv.resize(new_size); for (int i = sz; i < new_size; ++i) _fac[i] = _fac[i - 1] * i; _fac_inv[new_size - 1] = U(1) / _fac[new_size - 1]; for (int i = new_size - 1; i > sz; --i) _fac_inv[i - 1] = _fac_inv[i] * i; } T fac(const int i) { ensure(i); return _fac[i]; } T operator()(int i) { return fac(i); } U fac_inv(const int i) { ensure(i); return _fac_inv[i]; } U binom(const int n, const int r) { if (n < 0 or r < 0 or n < r) return 0; ensure(n); return _fac[n] * _fac_inv[r] * _fac_inv[n - r]; } template <typename ...Ds, std::enable_if_t<std::conjunction_v<std::is_integral<Ds>...>, std::nullptr_t> = nullptr> U polynom(const int n, const Ds& ...ds) { if (n < 0) return 0; ensure(n); int sumd = 0; U res = _fac[n]; for (int d : { ds... }) { if (d < 0 or d > n) return 0; sumd += d; res *= _fac_inv[d]; } if (sumd > n) return 0; res *= _fac_inv[n - sumd]; return res; } U perm(const int n, const int r) { if (n < 0 or r < 0 or n < r) return 0; ensure(n); return _fac[n] * _fac_inv[n - r]; } private: static std::vector<T> _fac; static std::vector<U> _fac_inv; }; template <typename T, typename U> std::vector<T> factorial<T, U>::_fac{ 1 }; template <typename T, typename U> std::vector<U> factorial<T, U>::_fac_inv{ 1 }; } // namespace suisen #line 5 "library/math/util.hpp" namespace suisen { template <typename mint> mint random_walk_1d(int n, int x) { if (x < 0) x = -x; factorial<mint> fac(n); int m = n + x; return m & 1 ? 0 : fac.binom(n, m / 2); } template <typename mint> mint random_walk_2d(int n, int x, int y) { return random_walk_1d<mint>(n, x + y) * random_walk_1d<mint>(n, x - y); } template <typename mint, typename BinomialCoefficient> mint random_walk_1d(int n, int x, const BinomialCoefficient &binom_n) { if (x < 0) x = -x; int m = n + x; return m & 1 ? 0 : binom_n(m / 2); } template <typename mint, typename BinomialCoefficient> mint random_walk_2d(int n, int x, int y, const BinomialCoefficient &binom_n) { return random_walk_1d<mint>(n, x + y, binom_n) * random_walk_1d<mint>(n, x - y, binom_n); } } // namespace suisen #line 9 "test/src/math/util/abc240_g.test.cpp" int main() { int n, x, y, z; std::cin >> n >> x >> y >> z; suisen::factorial<mint> fac(n); mint ans = 0; for (int i = 0; i <= n; ++i) { int j = i - z; ans += fac.binom(n, i) * fac.binom(n - i, j) * suisen::random_walk_2d<mint>(n - i - j, x, y); } std::cout << ans.val() << std::endl; return 0; }