#782568 (C++17) No.2023 Tiling is Fun

提出ソース
結果

問題	No.2023 Tiling is Fun
コンテスト
ユーザー	atree
提出日時	2022-07-29 22:33:18
言語	C++17 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	8 ms / 2,000 ms
コード長	16,021 bytes
コンパイル時間	1,985 ms
コンパイル使用メモリ	199,828 KB
最終ジャッジ日時	2025-01-30 15:31:39
ジャッジサーバーID （参考情報）	judge3 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 2
other	AC * 18
権限があれば一括ダウンロードができます
ソースコード

raw source code
// template {{{
#include <bits/stdc++.h>
#if __has_include(<debug.hpp>)
#    include <debug.hpp>
#else
#    define dbg(...) static_cast<void>(0)
#endif

using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using usize = std::size_t;
using bit_t = u64;

constexpr auto operator""_i32(unsigned long long n) noexcept {
    return static_cast<std::int32_t>(n);
}
constexpr auto operator""_i64(unsigned long long n) noexcept {
    return static_cast<std::int64_t>(n);
}
constexpr auto operator""_u32(unsigned long long n) noexcept {
    return static_cast<std::uint32_t>(n);
}
constexpr auto operator""_u64(unsigned long long n) noexcept {
    return static_cast<std::uint64_t>(n);
}
constexpr auto operator""_uz(unsigned long long n) noexcept {
    return static_cast<size_t>(n);
}
constexpr auto operator""_bit(unsigned long long n) noexcept {
    return static_cast<bit_t>(n);
}

template<class T, T N = 2> inline constexpr auto INF = std::numeric_limits<T>::max() / N;

template<class T> constexpr inline std::enable_if_t<std::is_arithmetic_v<T>, T> power(T a, u32 b) {
    T ans = 1;
    for (; b; b >>= 1) {
        if (b & 1) ans *= a;
        a *= a;
    }
    return ans;
}

template<class T> constexpr inline auto TEN(u32 n) {
    return power(static_cast<T>(10), n);
}

constexpr inline auto countr_zero(bit_t n) -> int {
    return n == 0 ? 64 : __builtin_ctzll(n);
}
constexpr inline auto countl_zero(bit_t n) -> int {
    return n == 0 ? 64 : __builtin_clzll(n);
}
constexpr inline auto countr_one(bit_t n) -> int {
    return n == std::numeric_limits<bit_t>::max() ? 64 : countr_zero(compl n);
}
constexpr inline auto countl_one(bit_t n) -> int {
    return n == std::numeric_limits<bit_t>::max() ? 64 : countl_zero(compl n);
}
constexpr inline auto mask(u32 n) -> bit_t {
    return (static_cast<bit_t>(1) << n) - 1;
}
constexpr inline auto popcount(bit_t n) -> int {
    return __builtin_popcountll(n);
}
constexpr inline auto is_pow2(bit_t n) -> bool {
    return (n & (n - 1)) == 0;
}
constexpr inline auto msb(bit_t n) -> int {
    return 63 - countl_zero(n);
}
constexpr inline auto bit_ceil(bit_t n) -> bit_t {
    return is_pow2(n) ? n : static_cast<bit_t>(1) << msb(n);
}
constexpr inline auto bit_floor(bit_t n) -> bit_t {
    return is_pow2(n) ? n : static_cast<bit_t>(1) << (msb(n) + 1);
}

template<class T, class U = T> constexpr auto chmin(T& a, U&& b) -> bool {
    return b < a ? a = std::forward<U>(b), true : false;
}
template<class T, class U = T> constexpr auto chmax(T& a, U&& b) -> bool {
    return a < b ? a = std::forward<U>(b), true : false;
}

template<class> struct is_tuple_like: std::false_type {};
template<class... Ts> struct is_tuple_like<std::tuple<Ts...>>: std::true_type {};
template<class T1, class T2> struct is_tuple_like<std::pair<T1, T2>>: std::true_type {};
template<class T, std::size_t N> struct is_tuple_like<std::array<T, N>>: std::true_type {};

template<class, class = std::void_t<>> struct is_printable: std::false_type {};
template<class T> struct is_printable<T, std::void_t<decltype(std::cout << std::declval<T>())>>: std::true_type {};

template<class, class = std::void_t<>> struct is_iteratable: std::false_type {};
template<class T>
struct is_iteratable<T, std::void_t<decltype(std::begin(std::declval<T>()), std::end(std::declval<T>()))>>:
    std::true_type {};

template<class, class = std::void_t<>> struct has_val: std::false_type {};
template<class T> struct has_val<T, std::void_t<decltype(std::declval<T>().val())>>: std::true_type {};

template<class T> struct is_1indexed: std::false_type {};
#define INDEXED_IMPL(type) \
    struct type##_##1 {    \
        using base = type; \
    };                     \
    template<> struct is_1indexed<type##_##1>: std::true_type {};
INDEXED_IMPL(int)
INDEXED_IMPL(size_t)
INDEXED_IMPL(i32)
INDEXED_IMPL(u32)
INDEXED_IMPL(i64)
INDEXED_IMPL(u64)
INDEXED_IMPL(usize)
#undef INDEXED_IMPL

template<class F> struct rec_lambda {
    F f;
    explicit constexpr rec_lambda(F&& f): f(std::forward<F>(f)) {}
    template<class... Args> constexpr decltype(auto) operator()(Args&&... args) const {
        return f(*this, std::forward<Args>(args)...);
    }
};

template<class... Args> auto zip(const std::vector<Args>&... args) {
    std::size_t n = std::min({ std::size(args)... });
    std::vector<std::tuple<std::decay_t<Args>...>> ret(n);
    for (std::size_t i = 0; i < n; ++i) ret[i] = { args[i]... };
    return ret;
}

template<class T, size_t N> auto construct_vector(std::vector<size_t>& sizes, T x = std::decay_t<T>{}) {
    if constexpr (N == 1) {
        return std::vector<std::decay_t<T>>(sizes[0], x);
    } else {
        size_t size = sizes[N - 1];
        sizes.pop_back();
        return std::vector(size, construct_vector<T, N - 1>(sizes, x));
    }
}

template<class T, size_t N> decltype(auto) make_vector(size_t (&&sizes)[N], T&& x = std::decay_t<T>{}) {
    std::vector<size_t> s(N);
    for (size_t i = 0; i < N; ++i) s[i] = sizes[N - i - 1];
    if constexpr (std::is_invocable_v<std::decay_t<T>>) {
        auto ret = construct_vector<std::invoke_result_t<std::decay_t<T>>, N>(s);
        rec_lambda([](auto&& self, auto& v, auto&& f) {
            for (auto it = std::begin(v); it != std::end(v); ++it) {
                if constexpr (std::is_same_v<std::decay_t<decltype(*it)>, std::invoke_result_t<decltype(f)>>) *it = f();
                else self(*it, f);
            }
        })(ret, x);
        return ret;
    } else {
        return construct_vector<std::decay_t<T>, N>(s, x);
    }
}

template<class V> auto make_graph(size_t n, const std::vector<std::tuple<V, V>>& edges, bool is_directed = false) {
    std::vector graph(n, std::vector<size_t>{});
    for (const auto& [u, v]: edges) {
        graph[u].emplace_back(v);
        if (not is_directed) graph[v].emplace_back(u);
    }
    return graph;
}

template<class V, class W>
auto make_graph(size_t n, const std::vector<std::tuple<V, V, W>>& edges, bool is_directed = false) {
    std::vector graph(n, std::vector<std::pair<size_t, W>>{});
    for (const auto& [u, v, w]: edges) {
        graph[u].emplace_back(v, w);
        if (not is_directed) graph[v].emplace_back(u, w);
    }
    return graph;
}

__attribute__((constructor)) auto io_setup() noexcept {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout << std::fixed << std::setprecision(10);
    std::cerr << std::fixed << std::setprecision(10);
}

// Copyright (c) 2021 Mitama Lab | `tuple_scan`, `scan`, `in` are based on the code released under the ISC license. see
// https://opensource.org/licenses/ISC.
template<class Tp, std::size_t... I> inline decltype(auto) tuple_scan(Tp&, std::index_sequence<I...>);

inline auto scan = [](auto&... args) {
    return (..., [&] {
        if constexpr (is_tuple_like<std::decay_t<decltype(args)>>::value) {
            return tuple_scan(args, std::make_index_sequence<std::tuple_size_v<std::decay_t<decltype(args)>>>{});
        } else {
            return not (std::cin >> args).fail();
        }
    }());
};

template<class Tp, std::size_t... I> inline auto tuple_scan(Tp& tup, std::index_sequence<I...>) {
    return (... and scan(std::get<I>(tup)));
}

template<class T, class... Args> decltype(auto) inline in();

template<class Tp, std::size_t... I> inline auto tuple_in(std::index_sequence<I...>) {
    return std::tuple{ in<typename std::tuple_element_t<I, Tp>>()... };
}

template<class T, class... Args> decltype(auto) inline in() {
    if constexpr (sizeof...(Args) == 0) {
        if constexpr (is_tuple_like<T>::value) {
            auto t = tuple_in<T>(std::make_index_sequence<std::tuple_size_v<T>>());
            return t;
        } else if constexpr (is_1indexed<T>::value) {
            typename T::base x;
            scan(x);
            --x;
            return x;
        } else {
            T x;
            scan(x);
            return x;
        }
    } else {
        return std::tuple{ in<T>(), in<Args>()... };
    }
}

template<class T, class... size_t> inline auto in_vec(size_t&&... args) {
    return make_vector({ static_cast<usize>(args)... }, *in<T>);
}

inline constexpr char sep = ' ';
inline constexpr char eoln = '\n';
inline constexpr auto yes = "Yes";
inline constexpr auto no = "No";

inline auto print(){};

template<class T> inline auto print(T&&) -> void;

template<class Tp, std::size_t... I> inline auto tuple_print(Tp&& tp, std::index_sequence<I...>) -> void {
    (
        [&] {
            print(std::forward<decltype(std::get<I>(tp))>(std::get<I>(tp)));
            if constexpr (I + 1 != std::tuple_size_v<std::decay_t<Tp>>) print(sep);
        }(),
        ...);
}

template<class...> constexpr bool false_v = false;
template<class T> inline auto print(T&& x) -> void {
    if constexpr (is_printable<std::decay_t<T>>::value) {
        if constexpr (std::is_same_v<bool, std::decay_t<T>>) std::cout << (x ? yes : no);
        else std::cout << x;
    } else if constexpr (is_tuple_like<std::decay_t<T>>::value) {
        tuple_print(std::forward<T>(x), std::make_index_sequence<std::tuple_size_v<std::decay_t<T>>>());
    } else if constexpr (is_iteratable<T>::value) {
        for (auto it = std::begin(x); it != std::end(x); ++it) {
            print(std::forward<decltype(*it)>(*it));
            if (next(it) != std::end(x)) print(sep);
        }
    } else if (has_val<std::decay_t<T>>::value) {
        print(x.val());
    }
}

template<class T, class... Args> inline auto print(T&& t, Args&&... args) {
    print(std::forward<T>(t));
    print(sep);
    print(std::forward<Args>(args)...);
}

template<class... Args> inline auto println(Args&&... args) {
    print(std::forward<Args>(args)...);
    print(eoln);
}

template<class... Args> [[noreturn]] inline auto drop(Args&&... args) {
    println(std::forward<Args>(args)...);
    exit(0);
}

#define overload2(_NULL, _1, _2, name, ...) name
#define rep1(i, n) for (std::decay_t<decltype(n)> i = 0; i < (n); i++)
#define rep2(i, a, b) for (std::decay_t<decltype(b)> i = (a); i < (b); i++)
#define rep(...) overload2(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)
#define LAMBDA(...) [&]([[maybe_unused]] const auto& _) { return __VA_ARGS__; }
#define LAMBDA2(...) [&](const auto& _1, const auto& _2) { return __VA_ARGS__; }
// }}}

/**
 * @brief Modint
 */

/**
 * @brief Extended Euclid's Algorithm
 * @note return pair of minimum x, y s.t. ax + by = gcd(x, y)
 * @ref https://noshi91.hatenablog.com/entry/2019/04/01/184957
 */

constexpr std::pair<intmax_t, intmax_t> extgcd(intmax_t a, intmax_t b) {
    intmax_t s = a, xs = 1, ys = 0, t = b, xt = 0, yt = 1;
    while (s % t != 0) {
        const intmax_t tmp = s / t, u = s - t * tmp, xu = xs - xt * tmp, yu = ys - yt * tmp;
        s = t, xs = xt, ys = yt;
        t = u, xt = xu, yt = yu;
    }
    assert(t == std::gcd(a, b));
    return { xt, yt };
}

template<auto Modulo> struct Modint {
    using value_type = decltype(Modulo);

  private:
    value_type value = 0;
    template<class T> static constexpr value_type normalize(T n) {
        if (static_cast<std::common_type_t<value_type, T>>(n) >= Modulo) n %= Modulo;
        if (n < 0) (n %= Modulo) += Modulo;
        return n;
    }

  public:
    constexpr Modint() noexcept: value(0) {}
    template<class T, std::enable_if_t<std::is_integral_v<T>, std::nullptr_t> = nullptr>
    constexpr Modint(const T& n): value(normalize(n)) {}
    template<class T = value_type>
    constexpr std::enable_if_t<std::is_convertible_v<value_type, T>, T> val() const noexcept {
        return static_cast<T>(value);
    }
    template<class T = value_type>
    static constexpr std::enable_if_t<std::is_convertible_v<value_type, T>, T> mod() noexcept {
        return static_cast<T>(Modulo);
    }
    template<class T> static constexpr auto raw(const T& v) noexcept {
        Modint tmp{};
        tmp.value = static_cast<value_type>(v);
        return tmp;
    }

    constexpr auto operator+() const noexcept {
        return *this;
    }
    constexpr auto operator-() const noexcept {
        if (value == 0) return *this;
        return Modint::raw(mod() - value);
    }

    constexpr bool operator==(const Modint& rhs) {
        return value == rhs.value;
    }
    constexpr bool operator!=(const Modint& rhs) {
        return value != rhs.value;
    }

    constexpr auto& operator++() noexcept {
        if (++value == mod()) value = 0;
        return *this;
    }
    constexpr auto& operator--() noexcept {
        if (value-- == 0) value = mod() - 1;
        return *this;
    }
    constexpr auto operator++(int) {
        const auto tmp{ *this };
        ++*this;
        return tmp;
    }
    constexpr auto operator--(int) {
        const auto tmp{ *this };
        --*this;
        return tmp;
    }

    constexpr auto operator+(const Modint& rhs) const noexcept {
        return Modint{ *this } += rhs;
    }
    constexpr auto operator-(const Modint& rhs) const noexcept {
        return Modint{ *this } -= rhs;
    }
    constexpr auto operator*(const Modint& rhs) const noexcept {
        return Modint{ *this } *= rhs;
    }
    constexpr auto operator/(const Modint& rhs) const noexcept {
        return Modint{ *this } /= rhs;
    }

    constexpr auto& operator+=(const Modint& rhs) noexcept {
        if ((value += rhs.value) >= mod()) value -= mod();
        return *this;
    }
    constexpr auto& operator-=(const Modint& rhs) noexcept {
        if ((value -= rhs.value) < 0) value += mod();
        return *this;
    }
    constexpr auto& operator*=(const Modint& rhs) noexcept {
        value = static_cast<value_type>(static_cast<uint_fast64_t>(value) * static_cast<uint_fast64_t>(rhs.value)
                                        % mod());
        return *this;
    }
    constexpr auto& operator/=(const Modint& rhs) noexcept {
        return *this *= rhs.inv();
    }

    constexpr auto inv() const {
        return Modint{ extgcd(this->val(), this->mod()).first };
    }
    template<class T> constexpr auto pow(T n) const {
        auto a = *this, ans = raw(1);
        while (n != 0) {
            if (n & 1) ans *= a;
            a *= a;
            n >>= 1;
        }
        return ans;
    }

    constexpr friend std::ostream& operator<<(std::ostream& os, const Modint& arg) {
        os << arg.value;
        return os;
    }
    constexpr friend std::istream& operator>>(std::istream& os, Modint& arg) {
        os >> arg.value;
        return os;
    }
};

using Modint1000000007 = Modint<1000000007>;
using Modint998244353 = Modint<998244353>;

template<typename M> class ModTable {
    std::vector<M> m_fact, m_fact_inv, m_inv;

  public:
    constexpr ModTable() = default;
    constexpr ModTable(const size_t n): m_fact(n + 1), m_fact_inv(n + 1), m_inv(n + 1) {
        m_inv[1] = 1;
        for (size_t i = 2; i <= n; ++i) m_inv[i] = -m_inv[M::mod() % i] * (M::mod() / i);
        m_fact[0] = 1;
        for (size_t i = 0; i < n; i++) m_fact[i + 1] = m_fact[i] * M{ i + 1 };
        m_fact_inv[n] = m_fact[n].inv();
        for (size_t i = n; i--;) m_fact_inv[i] = m_fact_inv[i + 1] * M{ i + 1 };
    }
    constexpr auto inv(const int i) const {
        assert(i != 0);
        return m_inv[i];
    }
    constexpr auto fact(const int i) const {
        return m_fact[i];
    }
    constexpr auto fact_inv(const int i) const {
        return m_fact_inv[i];
    }
    constexpr auto perm(const int i, const int j) const {
        return i >= j ? fact(i) * fact_inv(i - j) : 0;
    }
    constexpr auto binom(const int i, const int j) const {
        if (i < 0 or j < 0 or i < j) return M::raw(0);
        return m_fact[i] * m_fact_inv[j] * m_fact_inv[i - j];
    }
    constexpr auto homo(const int i, const int j) const {
        if (i == 0 and j == 0) return M::raw(1);
        return binom(i + j - 1, j);
    }
};
using namespace std;

int main() {
    auto [a, b] = in<int, int>();
    --a;
    --b;
    println(ModTable<Modint998244353>(200000).binom(a + b, a));
}
yukicoder

結果

ソースコード
