Submission #68199117

---

Source Code Expand

#include <bits/stdc++.h>
#define SZ(x) ((int)(x).size())
#define ALL(x) begin(x), end(x)
#define REP(i, n) for (int i = 0; i < int(n); i++)
#define REP1(i, a, b) for (int i = (a); i <= int(b); i++)

#if __has_include("shik/dump.h")
#include "shik/dump.h"  // IWYU pragma: keep
#else
#define dump(...) 0
#endif

/// ModInt {{{
template <int M>
struct ModInt {
  int x_;
  constexpr ModInt() : x_() {}
  ModInt(std::integral auto x) {
    x_ = x % M;
    if (x_ < 0) x_ += M;
  }
  auto operator<=>(const ModInt&) const = default;

  ModInt operator-() const { return {x_ == 0 ? 0 : M - x_}; }
  ModInt& operator+=(ModInt rhs) {
    x_ += rhs.x_;
    if (x_ >= M) x_ -= M;
    return *this;
  }
  ModInt& operator-=(ModInt rhs) {
    x_ -= rhs.x_;
    if (x_ < 0) x_ += M;
    return *this;
  }
  ModInt& operator*=(ModInt rhs) {
    x_ = (int64_t)x_ * rhs.x_ % M;
    return *this;
  }
  ModInt& operator/=(ModInt rhs) { return *this *= rhs.inv(); }
  ModInt operator+(ModInt rhs) const { return ModInt(*this) += rhs; }
  ModInt operator-(ModInt rhs) const { return ModInt(*this) -= rhs; }
  ModInt operator*(ModInt rhs) const { return ModInt(*this) *= rhs; }
  ModInt operator/(ModInt rhs) const { return ModInt(*this) /= rhs; }

  ModInt inv() const {
    // precondition: gcd(x, M) = 1
    int a = x_, b = M, u = 1, v = 0;
    while (b != 0) {
      int t = a / b;
      a -= t * b;
      u -= t * v;
      std::swap(a, b);
      std::swap(u, v);
    }
    return u;
  }

  ModInt pow(std::integral auto e) {
    ModInt r = 1, p = *this;
    if (e < 0) {
      p = p.inv();
      e = -e;
    }
    while (e != 0) {
      if (e & 1) r *= p;
      p *= p;
      e >>= 1;
    }
    return r;
  }

  friend std::istream& operator>>(std::istream& is, ModInt& i) {
    return is >> i.x_;
  }
  friend std::ostream& operator<<(std::ostream& os, ModInt i) {
    return os << i.x_;
  }
};
/// }}}

using namespace std;
using mint = ModInt<998244353>;

const int N = 4e5 + 10;

mint fac[N], ifac[N];
void predo() {
  fac[0] = 1;
  for (int i = 1; i < N; i++) {
    fac[i] = fac[i - 1] * i;
  }
  ifac[N - 1] = fac[N - 1].inv();
  for (int i = N - 2; i >= 0; i--) {
    ifac[i] = ifac[i + 1] * (i + 1);
  }
}

mint C(int n, int m) {
  if (m < 0 || m > n) return 0;
  return fac[n] * ifac[m] * ifac[n - m];
}

mint A(int n, int m) {
  if (n < 0 || m < 0) return 0;
  return fac[n + m] * ifac[n] * ifac[m];
}

int n, m, k;
void input() {
  cin >> n >> m >> k;
}

mint solve_m2(int n, int m, int k) {
  return fac[k] * ifac[n - 1] * ifac[m - 1];
}

mint solve_m1(int n, int m, int k) {
  mint ans = solve_m2(n, m, n + m - 2);
  mint w = mint(n - 1) * m + mint(m - 1) * n;
  w -= n + m - 2;
  ans *= w;
  return ans;
}

mint solve_m0(int n, int m, int k) {
  mint ans = solve_m2(n, m, n + m - 2);
  mint w = mint(n - 1) * m + mint(m - 1) * n;
  w -= n + m - 2;
  ans *= w * (w - 1) * ifac[2];

  mint dup = fac[n + m - 3] * ifac[n - 2] * ifac[m - 2];
  ans -= dup;

  mint ext = 0;
  ext += A(n + 1, m - 3) * (n - 1);
  ext += A(m + 1, n - 3) * (m - 1);
  ans += ext;

  return ans;
}

mint solve() {
  if (k < n + m - 2) return 0;
  if (k == n + m - 2) return solve_m2(n, m, k);
  if (k == n + m - 1) return solve_m1(n, m, k);
  if (k == n + m) return solve_m0(n, m, k);
  assert(false);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  predo();
  int t;
  cin >> t;
  while (t--) {
    input();
    auto ans = solve();
    cout << ans << '\n';
  }
  return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘mint solve_m1(int, int, int)’:
Main.cpp:117:33: warning: unused parameter ‘k’ [-Wunused-parameter]
  117 | mint solve_m1(int n, int m, int k) {
      |                             ~~~~^
Main.cpp: In function ‘mint solve_m0(int, int, int)’:
Main.cpp:125:33: warning: unused parameter ‘k’ [-Wunused-parameter]
  125 | mint solve_m0(int n, int m, int k) {
      |                             ~~~~^

Judge Result