#1148877 (C++23) No.3450 Permutation of Even Scores

• 問題: No.3450 Permutation of Even Scores
• ユーザー: risujiroh
• 提出日時: 2026-02-20 23:07:29
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 7,710 bytes
• コンパイル時間: 6,089 ms
• コンパイル使用メモリ: 371,264 KB
• 実行使用メモリ: 13,420 KB
• 最終ジャッジ日時: 2026-02-20 23:08:47
• 合計ジャッジ時間: 21,676 ms
• ジャッジサーバーID （参考情報）: judge3 / judge1

ファイルパターン	結果
sample	AC * 4
other	AC * 45 WA * 1

ソースコード

#if __INCLUDE_LEVEL__ == 0

#include __BASE_FILE__

using Mint = atcoder::modint998244353;

Comb<Mint> comb;

void Solve() {
  int n, m;
  IN(n, m);
  basic_string<bool> s(n, false);
  s[0] = true;
  s[n - 1] = true;
  int parity = 0;
  while (m--) {
    int a;
    IN(a);
    if (a == 1 || a == n) {
      parity ^= 1;
    } else {
      s[a - 1] = true;
    }
  }

  vector<Mint> f(n);
  f[0] = -comb.Inv(4);

  /* for (int i : Rep(0, n)) {
    if (s[i]) {
      for (int j : Rep(i + 1, n)) {
        f[j] -= 2 * comb.Fact(j - i + 1) * f[i];
      }
    } else {
      f[i] = 0;
    }
  } */

  Fix([&](auto self, int L, int R) -> void {
    if (L + 1 == R) {
      if (!s[L]) {
        f[L] = 0;
      }
      return;
    }
    int M = midpoint(L, R);
    self(L, M);
    /* for (int i : Rep(0, R - M)) {
      for (int j : Rep(0, M - L)) {
        f[M + i] -= 2 * comb.Fact(i - j + M - L + 1) * f[L + j];
      }
    } */
    vector a(f.begin() + L, f.begin() + M);
    vector<Mint> b(R - L);
    for (int k : Rep(0, Len(b))) {
      b[k] = -2 * comb.Fact(k + 1);
    }
    a = atcoder::convolution(a, b);
    for (int i : Rep(0, R - M)) {
      f[M + i] += a[M - L + i];
    }
    self(M, R);
  })(0, n);

  Mint ans = comb.Fact(n) * comb.Inv(2) + (parity ? -f.back() : f.back());
  OUT(ans);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  Solve();
}

#elif __INCLUDE_LEVEL__ == 1

#include <bits/stdc++.h>

#include <atcoder/convolution.hpp>
#include <atcoder/modint.hpp>

template <class T>
class Comb {
 public:
  Comb() = default;

  explicit Comb(int n) {
    Reserve(n);
  }

  void Reserve(int n) {
    const int sz = static_cast<int>(fact_.size());
    if (n < sz) {
      return;
    }
    fact_.resize(n + 1);
    const int nsz = static_cast<int>(fact_.capacity());
    fact_.resize(nsz);
    fact_inv_.resize(nsz);
    for (int i = sz; i < nsz; ++i) {
      fact_[i] = T(i) * fact_[i - 1];
    }
    fact_inv_.back() = T(1) / fact_.back();
    for (int i = nsz; --i > sz;) {
      fact_inv_[i - 1] = fact_inv_[i] * T(i);
    }
  }

  T Fact(int n) {
    assert(n >= 0);
    Reserve(n);
    return fact_[n];
  }

  T FactInv(int n) {
    if (n < 0) {
      return T(0);
    }
    Reserve(n);
    return fact_inv_[n];
  }

  T FactRatio(int a, int b) {
    if (a >= 0) {
      return Fact(a) * FactInv(b);
    }
    assert(b < 0);
    const T t = FactRatio(~b, ~a);
    return (a - b) % 2 == 0 ? t : -t;
  }

  T Inv(int n) {
    assert(n != 0);
    return FactRatio(n - 1, n);
  }

  T Prod(std::ranges::iota_view<int, int> r) {
    return FactRatio(r.end()[-1], r[-1]);
  }

  T ProdInv(std::ranges::iota_view<int, int> r) {
    assert(r[0] > 0 || r.end()[-1] < 0);
    return FactRatio(r[-1], r.end()[-1]);
  }

  T Perm(int n, int k) {
    assert(n >= 0 ? true : k > n);
    return FactRatio(n, n - k);
  }

  T PermInv(int n, int k) {
    assert(n >= 0 ? k <= n : true);
    return FactRatio(n - k, n);
  }

  T Binom(int n, int k) {
    k = std::max(k, n - k);
    return Perm(n, k) * FactInv(k);
  }

  T BinomInv(int n, int k) {
    assert(n >= 0 ? 0 <= k && k <= n : 0 <= k || k <= n);
    k = std::max(k, n - k);
    return PermInv(n, k) * Fact(k);
  }

  T Multinom(std::span<const int> ks) {
    if (ks.size() < 2) {
      return T(1);
    }
    const int n = std::reduce(ks.begin(), ks.end());
    const int& min_k = *std::ranges::min_element(ks);
    T ret = FactRatio(n, min_k);
    for (const int& k : ks) {
      if (&k != &min_k) {
        ret *= FactInv(k);
      }
    }
    return ret;
  }

  template <class... Ks>
  requires(...&& std::same_as<Ks, int>)
      T Multinom(Ks... ks) {
    return Multinom(std::initializer_list<int>{ks...});
  }

  T MultinomInv(std::span<const int> ks) {
    if (ks.size() < 2) {
      return T(1);
    }
    const int n = std::reduce(ks.begin(), ks.end());
    const int& min_k = *std::ranges::min_element(ks);
    assert(n >= 0 ? min_k >= 0
                  : std::ranges::all_of(ks, [&](auto& k) { return &k == &min_k || k >= 0; }));
    T ret = FactRatio(min_k, n);
    for (const int& k : ks) {
      if (&k != &min_k) {
        ret *= Fact(k);
      }
    }
    return ret;
  }

  template <class... Ks>
  requires(...&& std::same_as<Ks, int>)
      T MultinomInv(Ks... ks) {
    return MultinomInv(std::initializer_list<int>{ks...});
  }

  T Homogeneous(int n, int k) {
    return Binom(n + k - 1, k);
  }

  T Catalan(int n) {
    assert(n >= 0);
    return Fact(2 * n) * FactInv(n) * FactInv(n + 1);
  }

  T Catalan(int n, int k) {
    assert(0 <= k && k <= n);
    return T(n - k + 1) * Fact(n + k) * FactInv(n + 1) * FactInv(k);
  }

 private:
  std::vector<T> fact_{T(1)};
  std::vector<T> fact_inv_{T(1)};
};

template <class F>
class Fix {
 public:
  explicit Fix(F f) : f_(std::move(f)) {}

  template <class... Ts>
  decltype(auto) operator()(Ts&&... xs) {
    return f_(std::ref(*this), std::forward<Ts>(xs)...);
  }

  template <class... Ts>
  decltype(auto) operator()(Ts&&... xs) const {
    return f_(std::ref(*this), std::forward<Ts>(xs)...);
  }

 private:
  F f_;
};

template <class T>
concept MyRange =
    std::ranges::range<T> &&
    !std::convertible_to<T, std::string_view> &&
    !std::convertible_to<T, std::filesystem::path>;

template <class T>
concept MyTuple = std::__is_tuple_like<T>::value && !MyRange<T>;

namespace std {

istream& operator>>(istream& is, MyRange auto&& r) {
  for (auto&& e : r) {
    is >> e;
  }
  return is;
}

istream& operator>>(istream& is, MyTuple auto&& t) {
  apply([&](auto&... xs) { (is >> ... >> xs); }, t);
  return is;
}

ostream& operator<<(ostream& os, MyRange auto&& r) {
  auto sep = "";
  for (auto&& e : r) {
    os << exchange(sep, " ") << forward<decltype(e)>(e);
  }
  return os;
}

ostream& operator<<(ostream& os, MyTuple auto&& t) {
  auto sep = "";
  apply([&](auto&... xs) { ((os << exchange(sep, " ") << xs), ...); }, t);
  return os;
}

template <class T, atcoder::internal::is_modint_t<T>* = nullptr>
istream& operator>>(istream& is, T& x) {
  int v;
  is >> v;
  x = T::raw(v);
  return is;
}

template <class T, atcoder::internal::is_modint_t<T>* = nullptr>
ostream& operator<<(ostream& os, const T& x) {
  return os << x.val();
}

}  // namespace std

template <class T>
class OneBased {
 public:
  explicit OneBased(T&& x) : ref_(std::forward<T>(x)) {}

  template <class... Ts>
  requires(sizeof...(Ts) > 1)
      OneBased(Ts&&... xs) : ref_(std::forward_as_tuple(std::forward<Ts>(xs)...)) {}

  friend std::istream& operator>>(std::istream& is, OneBased x) {
    if constexpr (MyRange<T>) {
      for (auto&& e : x.ref_) {
        is >> ::OneBased(e);
      }
    } else if constexpr (MyTuple<T>) {
      std::apply([&](auto&... xs) { (is >> ... >> ::OneBased(xs)); }, x.ref_);
    } else {
      is >> x.ref_;
      --x.ref_;
    }
    return is;
  }

  friend std::ostream& operator<<(std::ostream& os, OneBased x) {
    if constexpr (MyRange<T>) {
      auto f = [](auto&& e) { return ::OneBased(std::forward<decltype(e)>(e)); };
      os << (x.ref_ | std::views::transform(f));
    } else if constexpr (MyTuple<T>) {
      std::apply([&](auto&... xs) { os << std::tuple(::OneBased(xs)...); }, x.ref_);
    } else {
      os << ++x.ref_;
      --x.ref_;
    }
    return os;
  }

 private:
  T ref_;
};

template <class T>
OneBased(T&&) -> OneBased<T>;

template <class... Ts>
OneBased(Ts&&...) -> OneBased<std::tuple<Ts...>>;

using namespace std;

#define Rep(...) [](int l, int r) { return views::iota(min(l, r), r); }(__VA_ARGS__)
#define Len(r) int(size(r))
#define IN(...) (cin >> forward_as_tuple(__VA_ARGS__))
#define OUT(...) (cout << forward_as_tuple(__VA_ARGS__) << '\n')

#endif  // __INCLUDE_LEVEL__ == 1