raybbian's CP Algos

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub raybbian/comp-programming

:warning: main.cpp

Depends on

Code

#include "algo/common.h"
#include "algo/debug/preamble.h"

/* start include */
#include "algo/math/combo.h"
#include "algo/math/modint.h"
/* end include */

#include "algo/debug/debug.h"

using namespace std;
using namespace algo;

using mint = math::static_modint<998244353>;
math::combo<mint> C;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n - 1);
    for (int i = 0; i < n - 1; i++) {
        cin >> a[i];
    }
    // for s_i = a_i, then we must have that s_i is max on one side or the other
    // if we say that it is the max on the side that gets smaller as we iterate
    // then, we must have the max always decreases
    // some LIS/increasing subsequence thing
    // max on other side is awlays N
    // aggregate some number of Ns on the ends
    // if N position is fixed at end, then s_i must be increasing at (they must
    // all be start half)
    // in that case, the number of such permutations is every time that it
    // increases, then p_i = s_i
    // (choose s_i - num_increases, num_consecutive - 1)
    // we can treat s_i as max so far, or max on other side

    // num permutations that match s_i to index i, both directions

    // we have every distinct number up to peak is fixed.
    // for X spots, we must have <= K
    // for Y spots, we must have <= J

    // 3 1 4 5 2
    // 3 1 5 4 2
    // highest bucket: some permutation of numbers must happen
    // 3 _ 6 _ _ 5
    // 3 _ 5 _ _ 6
    // we choose from smallest to largest
    // doesn't matter what we choose, because the other is eligible anyways
    // 3 -> 2 less, (2, 1)
    // 5 -> 4-2 less -> (3, 2)
    // a is prefix maxes left of n, then suffix maxes right of n, so it has to
    // rise then fall
    int ptr = 0;
    while (ptr + 1 < n - 1 && a[ptr] <= a[ptr + 1]) {
        ptr++;
    }
    while (ptr + 1 < n - 1 && a[ptr] >= a[ptr + 1]) {
        ptr++;
    }
    if (ptr != n - 2) {
        dbg(a, "bad, not peak");
        cout << 0 << '\n';
        return;
    }
    vector<int> fst(n + 1, -1), lst(n + 1, -1);
    int last_seen = -1;
    for (int i = 0; i < n - 1; i++) {
        if (last_seen != a[i] && fst[a[i]] != -1) {
            // if last_seen is not itself, but we've seen before, then we bad
            dbg(i, a, "bad, dup num");
            cout << 0 << '\n';
            return;
        }
        if (last_seen != a[i]) {
            fst[a[i]] = i;
        }
        lst[a[i]] = i;
        last_seen = a[i];
    }
    int mx_el = *max_element(a.begin(), a.end());
    if (mx_el != n - 1) {
        dbg("bad max val");
        cout << 0 << '\n';
        return;
    }
    mint ans = 1;
    int num_used = 0;
    for (int el = 1; el <= mx_el; el++) {
        if (fst[el] == -1) {
            continue;
        }
        int len = lst[el] - fst[el];
        int num_avail = el - num_used - 1;
        if (num_avail < len) {
            dbg(el, num_avail, len, "bad, not enough num");
            cout << 0 << '\n';
            return;
        }
        ans *= C.perm(num_avail, len);
        if (el == mx_el) {
            // one edge must be highest value
            ans *= 2;
        }
        dbg(el, fst[el], lst[el], num_avail, ans);
        // we used len + 1 numbers
        num_used += len + 1;
    }
    cout << ans << '\n';
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--)
        solve();
}

#line 2 "algo/common.h"
#ifndef PREPROCESS
#include <bits/stdc++.h>
#include <cassert>
#endif

namespace algo {

// Indices and sizes into library containers. Signed, so the usual "walk down to
// -1" loops still terminate; widening the whole library is a change here alone.
using index_t = int;

} // namespace algo
#line 3 "algo/debug/preamble.h"

template <typename T>
concept printable = requires(T t) {
    { std::cout << t } -> std::same_as<std::ostream &>;
};
template <typename T>
concept iterable = std::ranges::range<T> && (!printable<T>);

template <typename... T>
inline void no_debug(T... _) {
}

template <size_t N>
std::ostream &operator<<(std::ostream &os, const std::bitset<N> &v);
template <typename T, typename U>
std::ostream &operator<<(std::ostream &os, std::queue<T, U> q);
template <typename T, typename U, typename V>
std::ostream &operator<<(std::ostream &os, std::priority_queue<T, U, V> pq);
template <typename T, typename U>
std::ostream &operator<<(std::ostream &os, const std::pair<T, U> &p);
template <typename... T>
std::ostream &operator<<(std::ostream &os, const std::tuple<T...> &t);
template <iterable T>
std::ostream &operator<<(std::ostream &os, const T &t);
#line 3 "main.cpp"

/* start include */
#line 3 "algo/math/common.h"

namespace algo::math {

constexpr int64_t safe_mod(int64_t x, int64_t m) {
    x %= m;
    if (x < 0) x += m;
    return x;
}

// Returns (x ** n) % m
constexpr int64_t pow_mod_constexpr(int64_t x, int64_t n, int m) {
    assert(0 <= n);
    assert(1 <= m);
    if (m == 1) return 0;
    unsigned int _m = (unsigned int)(m);
    uint64_t r = 1;
    uint64_t y = safe_mod(x, m);
    while (n) {
        if (n & 1) r = (r * y) % _m;
        y = (y * y) % _m;
        n >>= 1;
    }
    return r;
}

struct barrett {
    constexpr explicit barrett(uint64_t _m) : m(_m), im(-1ULL / _m) {
        assert(1 <= _m);
    }
    uint64_t mod() const {
        return m;
    };
    uint64_t reduce(uint64_t a) const {
        uint64_t q = (uint64_t)((__uint128_t(im) * a) >> 64);
        uint64_t r = a - q * m;
        return r - (r >= m) * m;
    }

private:
    uint64_t m, im;
};

constexpr int64_t c_div(int64_t a, int64_t b) {
    return a / b + ((a ^ b) > 0 && a % b);
}
constexpr int64_t f_div(int64_t a, int64_t b) {
    return a / b - ((a ^ b) < 0 && a % b);
}

auto bpow(auto const &x, auto n, auto const &one, auto op) {
    if (n == 0) {
        return one;
    } else {
        auto t = bpow(x, n / 2, one, op);
        t = op(t, t);
        if (n % 2) {
            t = op(t, x);
        }
        return t;
    }
}
auto bpow(auto x, auto n, auto ans) {
    return bpow(x, n, ans, std::multiplies{});
}
template <typename T>
T bpow(T const &x, auto n) {
    return bpow(x, n, T(1));
}

// Returns a pair(g, x) s.t. g = gcd(a, n), xa = g (mod n), 0 <= x < n/g
// If r > 1 then a is not invertible mod n
constexpr std::pair<int64_t, int64_t> inv_gcd(int64_t a, int64_t n) {
    a = safe_mod(a, n);
    if (a == 0) return {n, 0};

    int64_t t = 0, newt = 1;
    int64_t r = n, newr = a;

    while (newr) {
        int64_t quotient = r / newr;
        r -= newr * quotient;
        t -= newt * quotient;

        std::swap(r, newr);
        std::swap(t, newt);
    }
    if (t < 0) t += n / r;
    return {r, t};
}

} // namespace algo::math
#line 4 "algo/math/combo.h"

namespace algo::math {

// Factorial tables sized on demand by doubling. State lives here rather than in
// statics, so two moduli are two objects and neither can go stale.
template <typename T>
struct combo {
    explicit combo(index_t n = 0) {
        if (n > 0) fact(n), inv_fact(n);
    }

    T fact(index_t n) {
        if (n >= (index_t)f.size()) {
            assert(n < mod());
            if (f.empty()) f.push_back(T(1));
            index_t m = grow_to(n, (index_t)f.size());
            f.reserve(m);
            for (index_t i = (index_t)f.size(); i < m; i++) {
                f.push_back(f.back() * T(i));
            }
        }
        return f[n];
    }
    T inv_fact(index_t n) {
        if (n >= (index_t)inv_f.size()) {
            assert(n < mod());
            if (inv_f.empty()) inv_f.push_back(T(1));
            index_t lo = (index_t)inv_f.size(), m = grow_to(n, lo);
            inv_f.resize(m);
            inv_f[m - 1] = T(1) / fact(m - 1);
            for (index_t i = m - 2; i >= lo; i--) {
                inv_f[i] = inv_f[i + 1] * T(i + 1);
            }
        }
        return inv_f[n];
    }
    T cmb(index_t n, index_t r) {
        if (r < 0 || r > n) {
            return T(0);
        } else {
            return fact(n) * inv_fact(r) * inv_fact(n - r);
        }
    }
    T perm(index_t n, index_t r) {
        if (r < 0 || r > n) {
            return T(0);
        } else {
            return fact(n) * inv_fact(n - r);
        }
    }

private:
    std::vector<T> f, inv_f;

    static int mod() {
        if constexpr (requires { T::mod(); }) {
            return T::mod();
        } else {
            return std::numeric_limits<int>::max();
        }
    }
    // n! is 0 once n >= mod (mod divides it) and has no inverse, so neither
    // table grows past the modulus.
    static index_t grow_to(index_t n, index_t cur) {
        return std::min<int64_t>(std::max<int64_t>(n + 1, 2LL * cur), mod());
    }
};

} // namespace algo::math
#line 4 "algo/math/modint.h"

namespace algo::math {

// A modulus fixed at compile time: no state, and the division folds into a
// multiply-shift.
template <int Mod>
struct static_mod {
    static constexpr int mod() {
        return Mod;
    }
    static int reduce(uint64_t x) {
        return (int)(x % (uint64_t)Mod);
    }
};

// A modulus known only at run time, held for the extent of with_mod. Nesting is
// rejected: values built under the outer modulus would survive into the inner
// one. Use a second id to hold two moduli at once.
template <int id>
struct dynamic_mod {
    static int mod() {
        assert(armed);
        return bt.mod();
    }
    static int reduce(uint64_t x) {
        return (int)bt.reduce(x);
    }
    static auto with_mod(int m, auto callback) {
        assert(1 <= m && !armed);
        struct scoped {
            ~scoped() {
                armed = false;
            }
        } _;
        bt = barrett(m), armed = true;
        return callback();
    }

private:
    static inline barrett bt{1};
    static inline bool armed = false;
};

// P supplies mod() and reduce(). Inheriting it makes both reachable through the
// modint (as is with_mod), and an empty policy costs no space.
template <typename P>
struct modint : P {
    modint() : v(0) {
    }
    modint(int64_t _v) {
        v = (-P::mod() < _v && _v < P::mod()) ? _v : _v % P::mod();
        if (v < 0) v += P::mod();
    }
    modint &operator+=(const modint &other) {
        v += other.v;
        if (v >= P::mod()) v -= P::mod();
        return *this;
    }
    modint &operator-=(const modint &other) {
        v -= other.v;
        if (v < 0) v += P::mod();
        return *this;
    }
    modint &operator*=(const modint &other) {
        v = P::reduce((uint64_t)v * other.v);
        return *this;
    }
    modint &operator/=(const modint &other) {
        return *this = *this * other.inv();
    }
    modint &operator++() {
        v++;
        if (v == P::mod()) v = 0;
        return *this;
    }
    modint &operator--() {
        if (v == 0) v = P::mod();
        v--;
        return *this;
    }
    modint operator++(int) {
        modint result = *this;
        ++*this;
        return result;
    }
    modint operator--(int) {
        modint result = *this;
        --*this;
        return result;
    }
    friend modint operator+(modint a, const modint &b) {
        return a += b;
    }
    friend modint operator-(modint a, const modint &b) {
        return a -= b;
    }
    friend modint operator*(modint a, const modint &b) {
        return a *= b;
    }
    friend modint operator/(modint a, const modint &b) {
        return a /= b;
    }
    friend modint operator-(modint a) {
        return 0 - a;
    }
    modint inv() const {
        auto eg = inv_gcd(v, P::mod());
        assert(eg.first == 1);
        return eg.second;
    }
    friend bool operator==(const modint &a, const modint &b) {
        return a.v == b.v;
    }
    friend bool operator!=(const modint &a, const modint &b) {
        return !(a == b);
    }
    explicit operator int() const {
        return v;
    }
    friend std::ostream &operator<<(std::ostream &os, const modint &a) {
        return os << a.v;
    }
    friend std::istream &operator>>(std::istream &is, modint &a) {
        is >> a.v;
        a.v = (-P::mod() < a.v && a.v < P::mod()) ? a.v : a.v % P::mod();
        if (a.v < 0) a.v += P::mod();
        return is;
    }

private:
    int v;
};

template <int Mod>
using static_modint = modint<static_mod<Mod>>;
template <int id = 0>
using dynamic_modint = modint<dynamic_mod<id>>;

} // namespace algo::math
#line 7 "main.cpp"
/* end include */

#line 4 "algo/debug/debug.h"

template <size_t N>
std::ostream &operator<<(std::ostream &os, const std::bitset<N> &v) {
    os << "<";
    for (size_t i = 0; i < N; i++) {
        os << static_cast<char>('0' + v[i]);
    }
    return os << ">";
}
template <typename T, typename U>
std::ostream &operator<<(std::ostream &os, std::queue<T, U> q) {
    os << "[";
    bool first = true;
    for (; !q.empty(); q.pop()) {
        if (!first) os << ", ";
        first = false;
        os << q.front();
    }
    return os << "]";
}
template <typename T, typename U, typename V>
std::ostream &operator<<(std::ostream &os, std::priority_queue<T, U, V> pq) {
    os << "[";
    bool first = true;
    for (; !pq.empty(); pq.pop()) {
        if (!first) os << ", ";
        first = false;
        os << pq.top();
    }
    return os << "]";
}
template <typename T, typename U>
std::ostream &operator<<(std::ostream &os, const std::pair<T, U> &p) {
    return os << "(" << p.first << ", " << p.second << ")";
}
template <typename... T>
std::ostream &operator<<(std::ostream &os, const std::tuple<T...> &t) {
    os << "(";
    bool first = true;
    auto print = [&os, &first](auto arg) {
        if (!first) os << ", ";
        first = false;
        os << arg;
    };
    std::apply([&print](auto &&...args) { (print(args), ...); }, t);
    return os << ")";
}
template <iterable T>
std::ostream &operator<<(std::ostream &os, const T &t) {
    os << "[";
    bool first = true;
    for (const auto &e : t) {
        if (!first) os << ", ";
        first = false;
        os << e;
    }
    return os << "]";
}

template <typename T>
void debug(std::string_view name, T var) {
    std::cout << "\x1B[31m";
    // # keeps the quotes on a literal, so dbg("hi") prints as a bare message
    // while a const char* variable is still named.
    if (!name.starts_with('"')) std::cout << name << ": ";
    std::cout << var << "\x1B[0m" << '\n';
    std::cout.flush();
}

// https://www.scs.stanford.edu/~dm/blog/va-opt.html
#define PARENS ()
#define EXPAND(...) EXPAND4(EXPAND4(EXPAND4(EXPAND4(__VA_ARGS__))))
#define EXPAND4(...) EXPAND3(EXPAND3(EXPAND3(EXPAND3(__VA_ARGS__))))
#define EXPAND3(...) EXPAND2(EXPAND2(EXPAND2(EXPAND2(__VA_ARGS__))))
#define EXPAND2(...) EXPAND1(EXPAND1(EXPAND1(EXPAND1(__VA_ARGS__))))
#define EXPAND1(...) __VA_ARGS__
#define FOR_EACH(macro, ...)                                                   \
    __VA_OPT__(EXPAND(FOR_EACH_HELPER(macro, __VA_ARGS__)))
#define FOR_EACH_HELPER(macro, a1, ...)                                        \
    macro(a1) __VA_OPT__(FOR_EACH_AGAIN PARENS(macro, __VA_ARGS__))
#define FOR_EACH_AGAIN() FOR_EACH_HELPER

#define DEBUG(x) debug(#x, x);
#ifdef LOCAL
#define dbg(...) FOR_EACH(DEBUG, __VA_ARGS__) no_debug()
#else
#define dbg(...) no_debug(__VA_ARGS__)
#endif
#line 10 "main.cpp"

using namespace std;
using namespace algo;

using mint = math::static_modint<998244353>;
math::combo<mint> C;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n - 1);
    for (int i = 0; i < n - 1; i++) {
        cin >> a[i];
    }
    // for s_i = a_i, then we must have that s_i is max on one side or the other
    // if we say that it is the max on the side that gets smaller as we iterate
    // then, we must have the max always decreases
    // some LIS/increasing subsequence thing
    // max on other side is awlays N
    // aggregate some number of Ns on the ends
    // if N position is fixed at end, then s_i must be increasing at (they must
    // all be start half)
    // in that case, the number of such permutations is every time that it
    // increases, then p_i = s_i
    // (choose s_i - num_increases, num_consecutive - 1)
    // we can treat s_i as max so far, or max on other side

    // num permutations that match s_i to index i, both directions

    // we have every distinct number up to peak is fixed.
    // for X spots, we must have <= K
    // for Y spots, we must have <= J

    // 3 1 4 5 2
    // 3 1 5 4 2
    // highest bucket: some permutation of numbers must happen
    // 3 _ 6 _ _ 5
    // 3 _ 5 _ _ 6
    // we choose from smallest to largest
    // doesn't matter what we choose, because the other is eligible anyways
    // 3 -> 2 less, (2, 1)
    // 5 -> 4-2 less -> (3, 2)
    // a is prefix maxes left of n, then suffix maxes right of n, so it has to
    // rise then fall
    int ptr = 0;
    while (ptr + 1 < n - 1 && a[ptr] <= a[ptr + 1]) {
        ptr++;
    }
    while (ptr + 1 < n - 1 && a[ptr] >= a[ptr + 1]) {
        ptr++;
    }
    if (ptr != n - 2) {
        dbg(a, "bad, not peak");
        cout << 0 << '\n';
        return;
    }
    vector<int> fst(n + 1, -1), lst(n + 1, -1);
    int last_seen = -1;
    for (int i = 0; i < n - 1; i++) {
        if (last_seen != a[i] && fst[a[i]] != -1) {
            // if last_seen is not itself, but we've seen before, then we bad
            dbg(i, a, "bad, dup num");
            cout << 0 << '\n';
            return;
        }
        if (last_seen != a[i]) {
            fst[a[i]] = i;
        }
        lst[a[i]] = i;
        last_seen = a[i];
    }
    int mx_el = *max_element(a.begin(), a.end());
    if (mx_el != n - 1) {
        dbg("bad max val");
        cout << 0 << '\n';
        return;
    }
    mint ans = 1;
    int num_used = 0;
    for (int el = 1; el <= mx_el; el++) {
        if (fst[el] == -1) {
            continue;
        }
        int len = lst[el] - fst[el];
        int num_avail = el - num_used - 1;
        if (num_avail < len) {
            dbg(el, num_avail, len, "bad, not enough num");
            cout << 0 << '\n';
            return;
        }
        ans *= C.perm(num_avail, len);
        if (el == mx_el) {
            // one edge must be highest value
            ans *= 2;
        }
        dbg(el, fst[el], lst[el], num_avail, ans);
        // we used len + 1 numbers
        num_used += len + 1;
    }
    cout << ans << '\n';
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--)
        solve();
}
Back to top page