Submission #34072002

---

Source Code Expand

/*
[x^A y^B z^C] (1 - x*y*z) / (1 - x - y - z + 2*x*y*z)
[x^A y^B z^C] \sum_{i} (A-i+B-i+C-i+i)! /(i! (A-i)!(B-i)!(C-i)!) (-2)^i
*/

#include <iostream>

using i32 = int;
using u32 = unsigned;
using i64 = long long;

template <i32 MOD>
struct Mint {
  i32 n;
  constexpr Mint(i32 n = 0): n(n) {}
  constexpr Mint operator-() const { return Mint(n ? MOD - n: 0); }
  constexpr Mint &operator+=(const Mint &rhs){ n += rhs.n; if(n >= MOD) n -= MOD; return *this; }
  constexpr Mint &operator-=(const Mint &rhs){ if(rhs.n > n) n += MOD; n -= rhs.n; return *this; }
  constexpr Mint &operator*=(const Mint &rhs){ n = (i64) n * rhs.n % MOD; return *this; }
  constexpr Mint inv() const {
    i32 x = MOD;
    i32 y = n;
    i32 b = 0, d = 1;
    while(y){
      i32 q = x / y;
      x = x % y;
      b -= q * d;
      std::swap(x, y);
      std::swap(b, d);
    }
    if(b < 0) b += MOD;
    return b;
  }
  constexpr Mint &operator/=(const Mint &rhs){ n = (i64) n * rhs.inv().n % MOD; return *this; }
  friend constexpr Mint operator+(const Mint &lhs, const Mint &rhs){ return Mint(lhs) += rhs; }
  friend constexpr Mint operator-(const Mint &lhs, const Mint &rhs){ return Mint(lhs) -= rhs; }
  friend constexpr Mint operator*(const Mint &lhs, const Mint &rhs){ return Mint(lhs) *= rhs; }
  friend constexpr Mint operator/(const Mint &lhs, const Mint &rhs){ return Mint(lhs) /= rhs; }
  friend constexpr bool operator==(const Mint &lhs, const Mint &rhs){ return lhs.n == rhs.n; }
  friend constexpr bool operator!=(const Mint &lhs, const Mint &rhs){ return lhs.n != rhs.n; }
  friend std::ostream &operator<<(std::ostream &os, const Mint &rhs){ return os << rhs.n; }
};

constexpr i32 mod = 998244353;
using mint = Mint<mod>;

mint fact[3000001];
mint ifact[3000001];

int main(){
  i32 A, B, C;
  std::cin >> A >> B >> C;

  const i32 d = std::min(std::min(A, B), C);
  const i32 k = A + B + C;

  fact[0] = 1;
  for(i32 i = 1; i <= k; i++) fact[i] = i * fact[i-1];
  ifact[k] = fact[k].inv();
  for(i32 i = k-1; i >= 0; i--) ifact[i] = (i+1) * ifact[i+1];

  mint ans = 0;
  mint p = 1;

  for(i32 i = 0; i <= d; i++){
    ans += fact[A+B+C-2*i] * ifact[i] * ifact[A-i] * ifact[B-i] * ifact[C-i] * p;
    p *= mod-2;
  }

  p = 1;
  --A, --B, --C;
  for(i32 i = 0; i <= d; i++){
    ans -= fact[A+B+C-2*i] * ifact[i] * ifact[A-i] * ifact[B-i] * ifact[C-i] * p;
    p *= mod-2;
  }

  std::cout << ans << std::endl;

  return 0;
}

Submission Info

Judge Result