結果
問題 | No.2527 H and W |
ユーザー |
![]() |
提出日時 | 2023-11-03 22:47:52 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 30 ms / 2,000 ms |
コード長 | 9,662 bytes |
コンパイル時間 | 1,878 ms |
コンパイル使用メモリ | 198,276 KB |
最終ジャッジ日時 | 2025-02-17 18:39:20 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define rep(i, n) for (int i = 0; i < (n); i++)#define rep1(i, n) for (int i = 1; i <= (n); i++)#define rrep(i, n) for (int i = n - 1; i >= 0; i--)#define rrep1(i, n) for (int i = n; i >= 1; i--)#define all(x) x.begin(), x.end()#define rall(x) x.rbegin(), x.rend()#define eb emplace_back#define fi first#define se second#define sz(x) (int)(x).size()template <class T> using V = vector<T>;template <class T> using VV = V<V<T>>;typedef long long int ll;void speedUpIO() {cin.tie(nullptr);ios::sync_with_stdio(false);}template <class T> bool chmax(T& a, const T& b) {if (a < b) {a = b;return true;}return false;}template <class T> bool chmin(T& a, const T& b) {if (b < a) {a = b;return true;}return false;}#ifndef ATCODER_MODINT_HPP#define ATCODER_MODINT_HPP 1#include <atcoder/internal_math>#include <atcoder/internal_type_traits>#include <cassert>#include <numeric>#include <type_traits>#ifdef _MSC_VER#include <intrin.h>#endifnamespace atcoder {namespace internal {struct modint_base {};struct static_modint_base : modint_base {};template <class T> using is_modint = std::is_base_of<modint_base, T>;template <class T> using is_modint_t = std::enable_if_t<is_modint<T>::value>;} // namespace internaltemplate <int m, std::enable_if_t<(1 <= m)>* = nullptr> struct static_modint: internal::static_modint_base {using mint = static_modint;public:static constexpr int mod() {return m;}static mint raw(int v) {mint x;x._v = v;return x;}static_modint() : _v(0) {}template <class T, internal::is_signed_int_t<T>* = nullptr>static_modint(T v) {long long x = (long long)(v % (long long)(umod()));if (x < 0) x += umod();_v = (unsigned int)(x);}template <class T, internal::is_unsigned_int_t<T>* = nullptr>static_modint(T v) {_v = (unsigned int)(v % umod());}static_modint(bool v) {_v = ((unsigned int)(v) % umod());}unsigned int val() const {return _v;}mint& operator++() {_v++;if (_v == umod()) _v = 0;return *this;}mint& operator--() {if (_v == 0) _v = umod();_v--;return *this;}mint operator++(int) {mint result = *this;++*this;return result;}mint operator--(int) {mint result = *this;--*this;return result;}mint& operator+=(const mint& rhs) {_v += rhs._v;if (_v >= umod()) _v -= umod();return *this;}mint& operator-=(const mint& rhs) {_v -= rhs._v;if (_v >= umod()) _v += umod();return *this;}mint& operator*=(const mint& rhs) {unsigned long long z = _v;z *= rhs._v;_v = (unsigned int)(z % umod());return *this;}mint& operator/=(const mint& rhs) {return *this = *this * rhs.inv();}mint operator+() const {return *this;}mint operator-() const {return mint() - *this;}mint pow(long long n) const {assert(0 <= n);mint x = *this, r = 1;while (n) {if (n & 1) r *= x;x *= x;n >>= 1;}return r;}mint inv() const {if (prime) {assert(_v);return pow(umod() - 2);} else {auto eg = internal::inv_gcd(_v, m);assert(eg.first == 1);return eg.second;}}friend mint operator+(const mint& lhs, const mint& rhs) {return mint(lhs) += rhs;}friend mint operator-(const mint& lhs, const mint& rhs) {return mint(lhs) -= rhs;}friend mint operator*(const mint& lhs, const mint& rhs) {return mint(lhs) *= rhs;}friend mint operator/(const mint& lhs, const mint& rhs) {return mint(lhs) /= rhs;}friend bool operator==(const mint& lhs, const mint& rhs) {return lhs._v == rhs._v;}friend bool operator!=(const mint& lhs, const mint& rhs) {return lhs._v != rhs._v;}private:unsigned int _v;static constexpr unsigned int umod() {return m;}static constexpr bool prime = internal::is_prime<m>;};template <int id> struct dynamic_modint : internal::modint_base {using mint = dynamic_modint;public:static int mod() {return (int)(bt.umod());}static void set_mod(int m) {assert(1 <= m);bt = internal::barrett(m);}static mint raw(int v) {mint x;x._v = v;return x;}dynamic_modint() : _v(0) {}template <class T, internal::is_signed_int_t<T>* = nullptr>dynamic_modint(T v) {long long x = (long long)(v % (long long)(mod()));if (x < 0) x += mod();_v = (unsigned int)(x);}template <class T, internal::is_unsigned_int_t<T>* = nullptr>dynamic_modint(T v) {_v = (unsigned int)(v % mod());}dynamic_modint(bool v) {_v = ((unsigned int)(v) % mod());}unsigned int val() const {return _v;}mint& operator++() {_v++;if (_v == umod()) _v = 0;return *this;}mint& operator--() {if (_v == 0) _v = umod();_v--;return *this;}mint operator++(int) {mint result = *this;++*this;return result;}mint operator--(int) {mint result = *this;--*this;return result;}mint& operator+=(const mint& rhs) {_v += rhs._v;if (_v >= umod()) _v -= umod();return *this;}mint& operator-=(const mint& rhs) {_v += mod() - rhs._v;if (_v >= umod()) _v -= umod();return *this;}mint& operator*=(const mint& rhs) {_v = bt.mul(_v, rhs._v);return *this;}mint& operator/=(const mint& rhs) {return *this = *this * rhs.inv();}mint operator+() const {return *this;}mint operator-() const {return mint() - *this;}mint pow(long long n) const {assert(0 <= n);mint x = *this, r = 1;while (n) {if (n & 1) r *= x;x *= x;n >>= 1;}return r;}mint inv() const {auto eg = internal::inv_gcd(_v, mod());assert(eg.first == 1);return eg.second;}friend mint operator+(const mint& lhs, const mint& rhs) {return mint(lhs) += rhs;}friend mint operator-(const mint& lhs, const mint& rhs) {return mint(lhs) -= rhs;}friend mint operator*(const mint& lhs, const mint& rhs) {return mint(lhs) *= rhs;}friend mint operator/(const mint& lhs, const mint& rhs) {return mint(lhs) /= rhs;}friend bool operator==(const mint& lhs, const mint& rhs) {return lhs._v == rhs._v;}friend bool operator!=(const mint& lhs, const mint& rhs) {return lhs._v != rhs._v;}private:unsigned int _v;static internal::barrett bt;static unsigned int umod() {return bt.umod();}};template <int id> internal::barrett dynamic_modint<id>::bt = 998244353;using modint998244353 = static_modint<998244353>;using modint1000000007 = static_modint<1000000007>;using modint = dynamic_modint<-1>;namespace internal {template <class T> using is_static_modint =std::is_base_of<internal::static_modint_base, T>;template <class T> using is_static_modint_t =std::enable_if_t<is_static_modint<T>::value>;template <class> struct is_dynamic_modint : public std::false_type {};template <int id> struct is_dynamic_modint<dynamic_modint<id>>: public std::true_type {};template <class T> using is_dynamic_modint_t =std::enable_if_t<is_dynamic_modint<T>::value>;} // namespace internal} // namespace atcoder#endif // ATCODER_MODINT_HPP/*--------------------------------------------------*/typedef pair<int, int> P;typedef atcoder::modint998244353 mint;const int INF = 1e9;const ll LINF = 1e18;const int MX = 100010;// combination mod primestruct combination {V<mint> fact, ifact;combination(int n) : fact(n + 1), ifact(n + 1) {fact[0] = 1;for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i;ifact[n] = fact[n].inv();for (int i = n; i >= 1; --i) ifact[i - 1] = ifact[i] * i;}mint nCk(int n, int k) {if (k < 0 || k > n) return 0;return fact[n] * ifact[k] * ifact[n - k];}};void solve() {ll H, W, K;cin >> H >> W >> K;K = H * W - K;mint ans = 0;combination cmb(max(H, W));if (K == H * W) {rep(w, W + 1) ans += cmb.nCk(W, w);rep(h, H + 1) ans += cmb.nCk(H, h);ans -= 1;cout << ans.val() << endl;return;}rep(h, H) {if ((K - W * h) % (H - h) != 0) continue;ll w = (K - W * h) / (H - h);if (!(0 <= w && w <= W)) continue;ans += cmb.nCk(H, h) * cmb.nCk(W, w);}cout << ans.val() << endl;}int main() {speedUpIO();int t = 1;// cin >> t;while (t--) {solve();// cout << solve() << "\n";// cout << (solve() ? "YES" : "NO") << "\n";// cout << fixed << setprecision(15) << solve() << "\n";}return 0;}