#1193422 (C++23) No.2149 Vanitas Vanitatum

• 問題: No.2149 Vanitas Vanitatum
• ユーザー: iastm
• 提出日時: 2026-10-17 03:01:25
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 18 ms / 2,000 ms
• コード長: 8,469 bytes
• コンパイル時間: 1,273 ms
• コンパイル使用メモリ: 178,016 KB
• 実行使用メモリ: 14,972 KB
• 最終ジャッジ日時: 2026-10-17 03:01:40
• 合計ジャッジ時間: 3,273 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

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

ソースコード

#include <iostream>
#include <vector>
#include <atcoder/modint>
// #include <kotone/modint_utility>
// https://github.com/amiast/cpp-utility

#ifndef KOTONE_MODINT_UTILITY_HPP
#define KOTONE_MODINT_UTILITY_HPP 1

#include <vector>
#include <cassert>
// #include <kotone/internal_type_traits>
// https://github.com/amiast/cpp-utility

#ifndef KOTONE_INTERNAL_TYPE_TRAITS_HPP
#define KOTONE_INTERNAL_TYPE_TRAITS_HPP 1

#include <concepts>

namespace kotone {

template <typename T> concept number = std::is_arithmetic_v<T>;

template <typename T> concept signed_number = std::signed_integral<T> || std::floating_point<T>;

template <typename mint> concept compatible_modint = requires(mint a, mint b, int64_t x) {
    { mint::mod() } -> std::convertible_to<int>;
    mint{};
    mint{1};
    mint{x};

    { a + b }       -> std::same_as<mint>;
    { a - b }       -> std::same_as<mint>;
    { -a }          -> std::same_as<mint>;
    { a * b }       -> std::same_as<mint>;
    { a / b }       -> std::same_as<mint>;
    { a.inv() }     -> std::same_as<mint>;
    { a.pow(x) }    -> std::same_as<mint>;

    { a += b }      -> std::same_as<mint&>;
    { a -= b }      -> std::same_as<mint&>;
    { a *= b }      -> std::same_as<mint&>;
    { a /= b }      -> std::same_as<mint&>;

    { a == b }      -> std::convertible_to<bool>;
    { a != b }      -> std::convertible_to<bool>;
    { a.val() }     -> std::convertible_to<int>;
};

template <typename T> concept additive = requires(T a, T b) {
    T{};
    { a + b }       -> std::same_as<T>;
    { a - b }       -> std::same_as<T>;
    { -a }          -> std::same_as<T>;
    { a == b }      -> std::convertible_to<bool>;
    { a != b }      -> std::convertible_to<bool>;
};

template <typename T> concept mutable_additive = (
    additive<T>
    && requires(T a, T b) {
        { a += b }  -> std::same_as<T&>;
        { a -= b }  -> std::same_as<T&>;
        { ++a }     -> std::same_as<T&>;
        { --a }     -> std::same_as<T&>;
        { a++ }     -> std::same_as<T>;
        { a-- }     -> std::same_as<T>;
    }
);

}  // namespace kotone

#endif  // KOTONE_INTERNAL_TYPE_TRAITS

namespace kotone {

// Returns a length-`(n+1)` vector `reciprocal` such that `reciprocal[i]` is the modular inverse of `i`.
// The value of `reciprocal[0]` is undefined.
// Requires `mint::mod()` to be prime.
// Requires `1 <= n < mint::mod()`.
template <compatible_modint mint> std::vector<mint> reciprocals(int n) {
    int p = mint::mod();
    assert(1 <= n && n <= p);
    std::vector<mint> result(n + 1);
    result[1] = 1;
    for (int i = 2; i <= n; i++) {
        result[i] = -(p / i) * result[p % i];
    }
    return result;
}

// Returns a vector containing the first `n + 1` factorials (`0!, 1!, ..., n!`).
// Requires `n >= 0`.
template <compatible_modint mint> std::vector<mint> factorials(int n) {
    assert(n >= 0);
    std::vector<mint> result(n + 1);
    result[0] = 1;
    for (int i = 1; i <= n; i++) result[i] = i * result[i - 1];
    return result;
}

// Returns a vector of inverse factorials given the vector of factorials.
// Requires `vec_factorial` to match the format of the output of `factorials()`.
// Requires `mint::mod()` to be prime.
// Requires `1 <= vec_factorial.size() <= mint::mod()`.
template <compatible_modint mint> std::vector<mint> inv_factorials(const std::vector<mint> &vec_factorial) {
    int len = vec_factorial.size();
    int p = mint::mod();
    assert(1 <= len && len <= p);
    std::vector<mint> result(len);
    assert(vec_factorial[len - 1] != 0);
    result[len - 1] = vec_factorial[len - 1].inv();
    for (int i = len - 1; i > 0; i--) result[i - 1] = i * result[i];
    return result;
}

// A wrapper class for combinatorial functions with modint.
template <compatible_modint mint> struct modint_utility {
  private:
    std::vector<mint> _inv, _fact, _ifact;
    int _p = -1, _max_n = -1;

    void _build(int new_max) {
        if (new_max <= _max_n) return;
        _inv.resize(new_max + 1, 1);
        _fact.resize(new_max + 1, 1);
        _ifact.resize(new_max + 1, 1);
        for (int i = std::max(_max_n + 1, 2); i <= new_max; i++) {
            _inv[i] = -(_p / i) * _inv[_p % i];
        }
        for (int i = std::max(_max_n + 1, 2); i <= new_max; i++) _fact[i] = i * _fact[i - 1];
        for (int i = std::max(_max_n + 1, 2); i <= new_max; i++) _ifact[i] = _inv[i] * _ifact[i - 1];
        _max_n = new_max;
    }

  public:
    modint_utility() : _p(mint::mod()) {}

    // Instantiates with the first `n + 1` factorials (`0!, 1!, ..., n!`) precomputed.
    // Requires `mint::mod()` to be prime.
    // Requires `mint::mod()` to be invariant.
    // Requires `n < mint::mod()`.
    modint_utility(int n) {
        _p = mint::mod();
        assert(n < _p);
        _build(n);
    }

    // Returns the modular inverse of `n`.
    // Requires `1 <= n < mint::mod()`.
    mint inv(int n) {
        assert(1 <= n && n < _p);
        if (n >= _max_n) _build(n);
        return _inv[n];
    }

    // Returns `n!`.
    // Requires `0 <= n < mint::mod()`.
    mint factorial(int n) {
        assert(0 <= n && n < _p);
        if (n >= _max_n) _build(n);
        return _fact[n];
    }

    // Returns the modular inverse of `n!`.
    // Requires `0 <= n < mint::mod()`.
    mint inv_factorial(int n) {
        assert(0 <= n && n < _p);
        if (n >= _max_n) _build(n);
        return _ifact[n];
    }

    // Returns the number of permutations of `k` of `n` objects.
    // Requires `0 <= k <= n < mint::mod()`.
    mint perm(int n, int k) {
        assert(0 <= k && k <= n && n < _p);
        if (n >= _max_n) _build(n);
        return _fact[n] * _ifact[n - k];
    }

    // Returns the number of combinations of `k` of `n` objects.
    // Requires `0 <= k <= n < mint::mod()`.
    mint comb(int n, int k) {
        assert(0 <= k && k <= n && n < _p);
        if (n >= _max_n) _build(n);
        return _fact[n] * _ifact[k] * _ifact[n - k];
    }

    // Returns the `n`-th Catalan number.
    // Requires `0 <= n * 2 < _p`.
    mint catalan(int n) {
        assert(0 <= n && n * 2 < _p);
        if (n * 2 >= _max_n) _build(n * 2);
        return _fact[n * 2] * _ifact[n + 1] * _ifact[n];
    }
};

// Returns a square root of the given value.
// If no square root exists, returns `0`.
// If there are multiple square roots, the function may return any of them.
template <compatible_modint mint> mint sqrt_mint(mint val) {
    if (val == 0) return 0;
    int mod = mint::mod();
    if (mod == 2) return val;
    if (val.pow((mod - 1) / 2) == -1) return 0;
    if (mod % 4 == 3) return val.pow((mod + 1) / 4);

    int s = 0;
    int q = mod - 1;
    while (q % 2 == 0) {
        q /= 2;
        s++;
    }

    mint z = 2;
    while (z.pow((mod - 1) / 2) == 1) z++;
    mint c = z.pow(q);
    mint x = val.pow((q + 1) / 2);
    mint t = val.pow(q);

    while (t != 1) {
        int i = 0;
        mint tpow = t;
        while (tpow != 1 && i < s) {
            tpow *= tpow;
            i++;
        }
        if (i == s) return 0;
        mint b = c.pow(1 << (s - i - 1));
        x *= b;
        t *= b * b;
        c = b * b;
        s = i;
    }
    return x;
}

}  // namespace kotone

#endif  // KOTONE_MODINT_UTILITY_HPP

using mint = atcoder::modint998244353;

int main() {
    int N;
    std::cin >> N;
    std::vector<int> A(N);
    int total = 0;
    for (int &a : A) std::cin >> a, total += a;

    kotone::modint_utility<mint> util(total);
    std::vector<std::vector<int>> seq(2);
    int prev = 0, k = 0;
    for (int a : A) {
        while (prev < a) prev++, seq[k].push_back(1), k ^= 1;
        seq[k].push_back(0);
        k ^= 1;
    }

    int c0 = 0, c1 = 0;
    mint result = 1;
    for (int k = 0; k < 2; k++) {
        std::vector<int> young;
        int acc = 0;
        int m = seq[k].size();
        for (int i = m - 1; i >= 0; i--) {
            if (seq[k][i] == 0) acc++;
            else young.push_back(acc), c0 += acc;
        }
        result *= util.factorial(c0);
        int n = young.size();
        for (int i = 0; i < n; i++) {
            for (int j = 0, k = 0; j < young[i]; j++) {
                while (young[k] <= j) k++;
                result *= util.inv(young[i] - j + i - k);
            }
        }
        std::swap(c0, c1);
    }

    if ((c0 + c1) * 2 != total) std::cout << 0 << std::endl;
    else {
        result *= util.comb(c0 + c1, c0);
        std::cout << result.val() << std::endl;
    }
}