cp-documentation

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub zawa-tin/cp-documentation

:heavy_check_mark: Test/AtCoder/abc247_f.test.cpp

Depends on

Code

#define PROBLEM "https://atcoder.jp/contests/abc247/tasks/abc247_f"

#include "../../Src/Template/TypeAlias.hpp"
#include "../../Src/Template/VectorIO.hpp"
#include "../../Src/Number/ModInt.hpp"
#include "../../Src/Graph/Components/ConnectedComponents.hpp"

#include <iostream>
#include <vector>
#include <array>

using namespace zawa;
using m32 = StaticModInt<u32, 998244353>;

int main() {
    usize n; std::cin >> n;

    std::vector<m32> cyc(n + 1);

    std::array<m32, 2> dp1{ m32{1}, m32{} }, dp2{ m32{}, m32{1} };
    for (u32 i{} ; i < n ; i++) {
        cyc[i + 1] = dp1[true] + dp2[false] + dp2[true];
        std::array<m32, 2> nxt1, nxt2;
        nxt1[false] = dp1[true];
        nxt2[false] = dp2[true];
        nxt1[true] = dp1[false] + dp1[true];
        nxt2[true] = dp2[false] + dp2[true];
        dp1 = std::move(nxt1);
        dp2 = std::move(nxt2);
    }

    std::vector<u32> p(n), q(n);
    std::cin >> p >> q;
    ConnectedComponents cc(n);
    for (u32 i{} ; i < n ; i++) {
        cc.addEdge(p[i] - 1, q[i] - 1);
    }
    cc.build();

    m32 ans{1};
    for (u32 i{} ; i < cc.size() ; i++) {
        ans *= cyc[cc.n(i)];
    }
    std::cout << ans << std::endl;
}
#line 1 "Test/AtCoder/abc247_f.test.cpp"
#define PROBLEM "https://atcoder.jp/contests/abc247/tasks/abc247_f"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 2 "Src/Template/VectorIO.hpp"

#line 4 "Src/Template/VectorIO.hpp"

#include <iostream>
#include <vector>

namespace zawa {

template <class T>
std::istream &operator>>(std::istream& is, std::vector<T>& A) {
    for (T& a : A) {
        is >> a;
    }
    return is;
}

template <class T>
std::ostream &operator<<(std::ostream& os, const std::vector<T>& A) {
    for (u32 i{} ; i < A.size() ; i++) {
        os << A[i] << (i + 1 == A.size() ? "" : " ");
    }
    return os;
}

} // namespace zawa
#line 2 "Src/Number/ModInt.hpp"

#line 4 "Src/Number/ModInt.hpp"

#include <type_traits>
#line 7 "Src/Number/ModInt.hpp"
#include <utility>
#include <cassert>

namespace zawa {

template <class T, T mod>
class StaticModInt {
private:
    using mint = StaticModInt;

    T v_{};

    static constexpr void templateTypeAssert() {
        static_assert(std::is_integral_v<T>, "ModInt template argument must be integral");
        static_assert(mod > 0, "mod must be positive");
    }

    i64 extendGCD(i64 a, i64 b, i64& x, i64& y) const {
       i64 d{a};
       if (b) {
           d = extendGCD(b, a % b, y, x);
           y -= (a / b) * x;
       }
       else {
           x = 1;
           y = 0;
       }
       return d;
    }

public:

    constexpr StaticModInt() {
        templateTypeAssert();
    }
    template <class ArgType>
    constexpr StaticModInt(ArgType v) : v_{ static_cast<T>(((v % mod) + mod) % mod) } {
        templateTypeAssert();
        static_assert(std::is_integral_v<ArgType>, "ModInt constructor Argument Must Be Integral");
    }

    friend std::istream& operator>>(std::istream& is, mint& value) {
        is >> value.v_;
        return is;
    }
    friend std::ostream& operator<<(std::ostream& os, const mint& value) {
        os << value.v_;
        return os;
    }

    T v() const {
        return v_;
    }

    bool operator==(const mint& rhs) const {
        return v_ == rhs.v_;
    }

    mint operator+() const {
        return *this;
    }
    mint& operator+=(const mint& rhs) {
        v_ = (v_ < mod - rhs.v_ ? v_ + rhs.v_ : v_ + rhs.v_ - mod);
        return *this;
    }
    friend mint operator+(const mint& lhs, const mint& rhs) {
        return mint{lhs} += rhs;
    }
    mint& operator++() {
        v_ = (v_ + 1 == mod ? 0 : v_ + 1);
        return *this;
    }
    mint operator++(int) {
        mint res{*this};
        ++*this;
        return res;
    }

    mint operator-() const {
        return mod - v_;
    }
    mint& operator-=(const mint& rhs) {
        v_ = (v_ >= rhs.v_ ? v_ - rhs.v_ : v_ + (mod - rhs.v_));
        return *this;
    }
    friend mint operator-(const mint& lhs, const mint& rhs) {
        return mint{lhs} -= rhs;
    }
    mint& operator--() {
        v_ = (v_ ? v_ - 1 : mod - 1);
        return *this;
    }
    mint operator--(int) {
        mint res{*this};
        --*this;
        return res;
    }

    mint& operator*=(const mint& rhs) {
        u64 mult{ static_cast<u64>(v_) * static_cast<u64>(rhs.v_) };
        v_ = static_cast<T>(mult % mod);
        return *this;
    }
    friend mint operator*(const mint& lhs, const mint& rhs) {
        return mint{lhs} *= rhs;
    }

    mint inverse() const {
        i64 res{}, hoge{};
        assert(extendGCD(static_cast<i64>(v_), static_cast<i64>(mod), res, hoge) == 1);
        return mint{res};
    }
    mint& operator/=(const mint& rhs) {
        return *this *= rhs.inverse();
    }
    friend mint operator/(const mint& lhs, const mint& rhs) {
        return mint{lhs} /= rhs;
    }

    mint pow(u64 k) const {
        mint res{1}, base{k};
        while (k) {
            if (k & 1) res *= base;
            base *= base; 
            k >>= 1;
        }
        return res;
    }
};

} // namespace zawa
#line 2 "Src/Graph/Components/ConnectedComponents.hpp"

#line 4 "Src/Graph/Components/ConnectedComponents.hpp"

#include <limits>
#line 8 "Src/Graph/Components/ConnectedComponents.hpp"
#include <stack>
#include <algorithm>
#line 11 "Src/Graph/Components/ConnectedComponents.hpp"

namespace zawa {

class ConnectedComponents {
public:
    struct Edge {
    private:
        u32 u_, v_, id_;
    public:
        Edge(u32 u, u32 v, u32 id) : u_{ u }, v_{ v }, id_{ id } {}

        inline u32 u() const noexcept {
            return u_;
        }
        inline u32 v() const noexcept {
            return v_;
        }
        inline u32 id() const noexcept {
            return id_;
        }
    };

private:
    class Component {
    private:
        std::vector<u32> vs_, es_;
    public:
        Component() = default;
        Component(const std::vector<u32>& vs, const std::vector<u32>& es) : vs_{ vs }, es_{ es } {
            vs_.shrink_to_fit();
            es_.shrink_to_fit();
        }
        
        inline usize n() const noexcept {
            return vs_.size();
        }
        inline usize m() const noexcept {
            return es_.size();
        }
        const std::vector<u32>& vs() const noexcept {
            return vs_;
        }
        const std::vector<u32>& es() const noexcept {
            return es_;
        }
        bool hasCycle() const {
            return not (n() == m() + 1);
        }
    };

    constexpr static u32 INVALID_{ std::numeric_limits<u32>::max() };

    std::vector<std::vector<u32>> graph_;
    std::vector<std::pair<u32, u32>> edges_;

    std::vector<u32> indexV_, indexE_;
    std::vector<Component> components_;

    bool isBuilt;

    void dfs(u32 s) {
        indexV_[s] = components_.size();
        std::stack<u32> stk{ { s } };
        while (stk.size()) {
            u32 v{ stk.top() };
            stk.pop();
            for (auto x : graph_[v]) {
                if (indexV_[x] == INVALID_) {
                    indexV_[x] = components_.size();
                    stk.push(x);
                }
            }
        }
    }

    void buildComponents() {
        std::vector<std::vector<u32>> vs(components_.size()), es(components_.size());
        for (u32 v{} ; v < n() ; v++) {
            vs[indexV_[v]].emplace_back(v);
        }
        for (u32 e{} ; e < m() ; e++) {
            es[indexE_[e]].emplace_back(e);
        }
        for (u32 i{} ; i < components_.size() ; i++) {
            components_[i] = Component(vs[i], es[i]);
        }
        components_.shrink_to_fit();
    }

public:
    ConnectedComponents() = default;

    ConnectedComponents(usize n) 
        : graph_(n), edges_{}, indexV_(n, INVALID_), indexE_{}, components_{}, isBuilt{} {
        graph_.shrink_to_fit();
    }
    
    void addEdge(u32 u, u32 v) {
        assert(not isBuilt);
        graph_[u].emplace_back(v);
        graph_[v].emplace_back(u);
        edges_.emplace_back(u, v);
    }

    inline usize n() const noexcept {
        return graph_.size();
    }

    inline usize m() const noexcept {
        return edges_.size();
    }

    Edge edge(u32 e) const {
        assert(e < m());
        return Edge{ edges_[e].first, edges_[e].second, e };
    }

    void build() {
        assert(not isBuilt);
        edges_.shrink_to_fit();
        indexV_.shrink_to_fit();
        for (u32 v{} ; v < n() ; v++) {
            if (indexV_[v] == INVALID_) {
                dfs(v);
                components_.emplace_back();
            }
        }
        indexE_.resize(m());
        indexE_.shrink_to_fit();
        for (u32 e{} ; e < m() ; e++) {
            indexE_[e] = indexV_[edges_[e].first];
        }
        buildComponents();
        isBuilt = true;
    }

    inline u32 operator[](const u32 v) const noexcept {
        assert(isBuilt);
        assert(v < n());
        return indexV_[v];
    }

    inline u32 indexV(u32 v) const noexcept {
        assert(isBuilt);
        assert(v < n());
        return indexV_[v];
    }

    inline u32 indexE(u32 e) const noexcept {
        assert(isBuilt);
        assert(e < m());
        return indexE_[e];
    }

    inline bool same(u32 u, u32 v) const noexcept {
        assert(isBuilt);
        assert(u < n());
        assert(v < n());
        return indexV_[u] == indexV_[v];
    }

    inline usize size() const noexcept {
        assert(isBuilt);
        return components_.size();
    }

    inline usize n(u32 c) const noexcept {
        assert(isBuilt);
        assert(c < size());
        return components_[c].n();
    }

    inline const std::vector<u32>& vs(u32 c) const noexcept {
        assert(isBuilt);
        assert(c < size());
        return components_[c].vs();
    }

    inline usize m(u32 c) const noexcept {
        assert(isBuilt);
        assert(c < size());
        return components_[c].m();
    }

    inline const std::vector<u32>& es(u32 c) const noexcept {
        assert(isBuilt);
        assert(c < size());
        return components_[c].es();
    }

    inline bool hasCycle(u32 c) const {
        assert(isBuilt);
        assert(c < size());
        return components_[c].hasCycle();
    }

};

} // namespace zawa
#line 7 "Test/AtCoder/abc247_f.test.cpp"

#line 10 "Test/AtCoder/abc247_f.test.cpp"
#include <array>

using namespace zawa;
using m32 = StaticModInt<u32, 998244353>;

int main() {
    usize n; std::cin >> n;

    std::vector<m32> cyc(n + 1);

    std::array<m32, 2> dp1{ m32{1}, m32{} }, dp2{ m32{}, m32{1} };
    for (u32 i{} ; i < n ; i++) {
        cyc[i + 1] = dp1[true] + dp2[false] + dp2[true];
        std::array<m32, 2> nxt1, nxt2;
        nxt1[false] = dp1[true];
        nxt2[false] = dp2[true];
        nxt1[true] = dp1[false] + dp1[true];
        nxt2[true] = dp2[false] + dp2[true];
        dp1 = std::move(nxt1);
        dp2 = std::move(nxt2);
    }

    std::vector<u32> p(n), q(n);
    std::cin >> p >> q;
    ConnectedComponents cc(n);
    for (u32 i{} ; i < n ; i++) {
        cc.addEdge(p[i] - 1, q[i] - 1);
    }
    cc.build();

    m32 ans{1};
    for (u32 i{} ; i < cc.size() ; i++) {
        ans *= cyc[cc.n(i)];
    }
    std::cout << ans << std::endl;
}
Back to top page