提出 #25619839

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, n) for (int i = a; i < (int)n; i++)
#define REP(i, n) FOR(i, 0, n)
#define FOREQ(i, a, n) FOR(i, a, n+1)


struct Mod {
  using lli = long long int;

  static constexpr lli M = 998244353;
  lli n;

  Mod(): n(0) {}
  Mod(long long int m): n(m) {
    if (m > M)
      n = m % M;
    else if (m < 0)
      n = (m % M + M) % M;
  }
  explicit operator lli() const { return n; }

  Mod& operator+=(const Mod& a) {
    n = (n + a.n) % M;
    return *this;
  }
  Mod& operator-=(const Mod& a) {
    n = (n + M - a.n) % M;
    return *this;
  }
  Mod& operator*=(const Mod& a) {
    n = (n * a.n) % M;
    return *this;
  }
  Mod operator/=(const Mod &a) {
    return *this *= Mod::inv(lli(a), M);
  }
  Mod operator+(const Mod& a) const {
    Mod res = *this;
    return res += a;
  }
  Mod operator-(const Mod& a) const {
    Mod res = *this;
    return res -= a;
  }
  Mod operator*(const Mod& a) const {
    Mod res = *this;
    return res *= a;
  }
  Mod operator/(const Mod &a) const {
    return *this * Mod::inv(lli(a), M);
  }
  Mod operator^(lli m) const {
    if (m == 0) return Mod(1);
    const Mod a = *this;
    Mod res = (a * a) ^ (m / 2);
    return m % 2 ? res * a : res;
  }
  static lli inv(lli a, lli p) {
    return (a == 1 ? 1 : (1 - p * inv(p % a, a)) / a + p);
  }
  static Mod fact(int n, bool sw = true) {
    static std::vector<Mod> v1 = { 1 }, v2 = { 1 };
    if (n >= (int)v1.size()) {
      const int from = v1.size(), to = n + 1024;
      v1.reserve(to);
      v2.reserve(to);
      for (int i = from; i < to; ++i) {
        v1.push_back(v1.back() * Mod(i));
        v2.push_back(v2.back() / Mod(i));
      }
    }
    return sw ? v1[n] : v2[n];
  }
  static Mod comb(int a, int b) {
    if (b == 0) return 1;
    if (b < 0 || b > a) return 0;
    return Mod::fact(a, true) * Mod::fact(b, false) *
           Mod::fact(a - b, false);
  }
};

istream& operator>>(istream& is, Mod& m) { return is >> m.n; }
ostream& operator<<(ostream& os, const Mod& m) { return os << m.n; }


int  N, M, A, B;
bool good[401][401];
Mod  memo[401][401];
bool used[401][401];

Mod loop(int first, int last) {
  if (used[first][last]) { return memo[first][last]; }

  used[first][last] = true;
  if (first == last) { return memo[first][last] = Mod(1); }

  Mod res(0);
  for (int mid = first + 2; mid <= last-2; mid += 2) {
    if (!good[first][mid-1]) { continue; }
    res += Mod::comb((last-first)/2, (mid-first)/2) * loop(first+1, mid-1) * loop(mid, last);
  }
  res += good[first][last-1] ? loop(first+1, last-1) : Mod(0);
  return memo[first][last] = res;
}

int main() {
  cin >> N >> M;
  REP(i, 401) REP(j, 401) { good[i][j] = used[i][j] = false; }
  REP(i, M) { cin >> A >> B; good[A-1][B-1] = good[B-1][A-1] = true; }
  cout << loop(0, 2*N) << endl;

  return 0;
}

提出情報

ジャッジ結果