Submission #33689796

---

Source Code Expand

#include <iostream>

using u32 = unsigned int;
using u64 = unsigned long long;

template <u32 MOD>
struct Mint {
  u32 n;
  constexpr Mint(u32 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 = (u64) n * rhs.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 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; }
};

template <class T>
T modpow(T x, int n){
  T r(1);
  for(; n; n >>= 1){
    if(n&1) r *= x;
    x *= x;
  }
  return r;
}

template <u32 MOD>
Mint<MOD> inv(Mint<MOD> n){
  return modpow(n, MOD-2);
}


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

mint fact[200001];
mint ifact[200001];

mint binom(int n, int k){ return k > n ? 0 : fact[n] * ifact[k] * ifact[n-k]; }

int deg[200000];

int main(){
  int n, m, k;
  std::cin >> n >> m >> k;
  fact[0] = 1;
  for(int i = 1; i <= n; i++) fact[i] = fact[i-1] * i;
  ifact[n] = inv(fact[n]);
  for(int i = n-1; i >=0; i--) ifact[i] = ifact[i+1] * (i+1);

  for(int i = 0; i < m; i++){
    int u, v;
    std::cin >> u >> v;
    --u, --v;
    deg[u]++, deg[v]++;
  }
  int count = 0;
  for(int i = 0; i < n; i++){
    if(deg[i] & 1) count++;
  }
  mint ans = 0;
  for(int i = 0; i <= k; i+=2){
    ans += binom(count, i) * binom(n - count, k - i);
  }
  std::cout << ans.n << std::endl;

  return 0;
}

Submission Info

Judge Result