#1141584 (C++17) No.2048 L(I+D)S

• 問題: No.2048 L(I+D)S
• ユーザー: Daniel Jiang
• 提出日時: 2025-12-24 14:53:57
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 49 ms / 2,000 ms
• コード長: 8,197 bytes
• コンパイル時間: 1,874 ms
• コンパイル使用メモリ: 201,192 KB
• 実行使用メモリ: 7,852 KB
• 最終ジャッジ日時: 2025-12-24 14:54:01
• 合計ジャッジ時間: 3,535 ms
• ジャッジサーバーID （参考情報）: judge3 / judge1

ファイルパターン	結果
sample	AC * 3
other	AC * 16

ソースコード

#include "bits/stdc++.h"
#ifdef DAN13
#include "../lib/debug.h"
#else
#define dbg(...) 69
#endif
using namespace std;
// containers
using ll = long long;
#define af(x) x.begin(), x.end()
#define pb push_back
// rng
mt19937 g1(chrono::steady_clock::now().time_since_epoch().count());
ll randint(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(g1); }
template <class T> void rem_dup(vector<T> &v) {
  sort(af(v));
  v.resize(unique(af(v)) - v.begin());
}
template <class T> bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template <class T> bool ckmax(T &a, const T &b) { return b > a ? a = b, 1 : 0; }
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;

template <typename T>
T inverse(T a, T m) {
  T u = 0, v = 1;
  while (a != 0) {
    T t = m / a;
    m -= t * a; swap(a, m); u -= t * v; swap(u, v);
  } assert(m == 1);
  return u;
}
template <typename T>
class Modular {
  public:
    using Type = typename decay<decltype(T::value)>::type;
    constexpr Modular() : value() {}
    template <typename U>
      Modular(const U& x) { value = normalize(x); }
    template <typename U>
      static Type normalize(const U& x) {
        Type v;
        if (-mod() <= x && x < mod()) v = static_cast<Type>(x);
        else v = static_cast<Type>(x % mod());
        if (v < 0) v += mod();
        return v;
      }
    const Type& operator()() const { return value; }
    template <typename U>
      explicit operator U() const { return static_cast<U>(value); }
    constexpr static Type mod() { return T::value; }
    Modular& operator+=(const Modular& other) {
      if ((value += other.value) >= mod()) value -= mod();
      return *this;
    }
    Modular& operator-=(const Modular& other) {
      if ((value -= other.value) < 0) value += mod();
      return *this;
    }
    template <typename U>
      Modular& operator+=(const U& other) { return *this += Modular(other); }
    template <typename U>
      Modular& operator-=(const U& other) { return *this -= Modular(other); }
    Modular& operator++() { return *this += 1; }
    Modular& operator--() { return *this -= 1; }
    Modular operator++(int) { Modular result(*this); *this += 1; return result; }
    Modular operator--(int) { Modular result(*this); *this -= 1; return result; }
    Modular operator-() const { return Modular(-value); }
    Modular operator+() const { return Modular(value); } // controversial?
    template <typename U = T>
      typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type& operator*=(const Modular& rhs) {
#ifdef _WIN32
        uint64_t x = static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value);
        uint32_t xh = static_cast<uint32_t>(x >> 32), xl = static_cast<uint32_t>(x), d, m;
        asm(
            "divl %4; \n\t"
            : "=a"(d), "=d"(m)
            : "d"(xh), "a"(xl), "r"(mod()));
        value = m;
#else
        value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
#endif
        return *this;
      }
    template <typename U = T>
      typename enable_if<is_same<typename Modular<U>::Type, long long>::value, Modular>::type& operator*=(const Modular& rhs) {
        long long q = static_cast<long long>(static_cast<long double>(value) * rhs.value / mod());
        value = normalize(value * rhs.value - q * mod());
        return *this;
      }
    template <typename U = T>
      typename enable_if<!is_integral<typename Modular<U>::Type>::value, Modular>::type& operator*=(const Modular& rhs) {
        value = normalize(value * rhs.value);
        return *this;
      }
    Modular& operator/=(const Modular& other) { return *this *= Modular(inverse(other.value, mod())); }
    friend const Type& abs(const Modular& x) { return x.value; }
    template <typename U>
      friend bool operator==(const Modular<U>& lhs, const Modular<U>& rhs);
    template <typename U>
      friend bool operator<(const Modular<U>& lhs, const Modular<U>& rhs);
    template <typename V, typename U>
      friend V& operator>>(V& stream, Modular<U>& number);
  private:
    Type value;
};
template <typename T>
bool operator==(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value == rhs.value; }
template <typename T, typename U>
bool operator==(const Modular<T>& lhs, U rhs) { return lhs == Modular<T>(rhs); }
template <typename T, typename U>
bool operator==(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) == rhs; }
template <typename T>
bool operator!=(const Modular<T>& lhs, const Modular<T>& rhs) { return !(lhs == rhs); }
template <typename T, typename U>
bool operator!=(const Modular<T>& lhs, U rhs) { return !(lhs == rhs); }
template <typename T, typename U>
bool operator!=(U lhs, const Modular<T>& rhs) { return !(lhs == rhs); }
template <typename T>
bool operator<(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value < rhs.value; }
template <typename T>
Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U>
Modular<T> operator+(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U>
Modular<T> operator+(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
template <typename T>
Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U>
Modular<T> operator-(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U>
Modular<T> operator-(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T>
Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U>
Modular<T> operator*(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U>
Modular<T> operator*(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T>
Modular<T> operator/(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }
template <typename T, typename U>
Modular<T> operator/(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) /= rhs; }
template <typename T, typename U>
Modular<T> operator/(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }
template <typename T, typename U>
Modular<T> power(const Modular<T>& a, const U& b) {
  assert(b >= 0);
  Modular<T> x = a, res = 1; U p = b;
  while (p > 0) {
    if (p & 1) res *= x;
    x *= x; p >>= 1;
  } return res;
}
template <typename T>
bool IsZero(const Modular<T>& number) { return number() == 0; }
template <typename T>
string to_string(const Modular<T>& number) { return to_string(number()); }
// U == std::ostream? but done this way because of fastoutput
template <typename U, typename T>
U& operator<<(U& stream, const Modular<T>& number) { return stream << number(); }
// U == std::istream? but done this way because of fastinput
template <typename U, typename T>
U& operator>>(U& stream, Modular<T>& number) {
  typename common_type<typename Modular<T>::Type, long long>::type x;
  stream >> x; number.value = Modular<T>::normalize(x);
  return stream;
}

constexpr int MOD = 998244353;
using mi = Modular<std::integral_constant<decay<decltype(MOD)>::type, MOD>>;
typedef vector<mi> vmi;

vmi fact, inv_fact;
mi choose(int n, int k) {
  if (k < 0 || k > n) { return 0; }
  if (fact.empty()) { fact.emplace_back(1); inv_fact.emplace_back(1); }
  while ((int) fact.size() < n + 1) {
    fact.push_back(fact.back() * (int) fact.size());
    inv_fact.push_back(1 / fact.back());
  } return fact[n] * inv_fact[k] * inv_fact[n - k];
}

void solve() { 
  // sum_{i=2}^n-2 ((n-1) * i * (i-2)! * n-i * (n - i - 2)!)^-2
  // sum_{i=2}^n-2 
  int n; cin >> n;
  choose(n, 0);
  mi ans = 0;
  for (int i = 2; i <= n - 2; i++) {
    mi cur = (mi)(n - 1) * (mi)i * (n - i) * fact[i - 2] * fact[n - i - 2];
    cur *= cur;
    ans += 1 / cur;
  }
  cout << ans * fact[n] * fact[n] << '\n';
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int tests = 1;
  // cin >> tests;
  for (int i = 1; i <= tests; i++) {
    solve();
  }
}