Test/AtCoder/abc307_e.test.cpp

View this file on GitHub
Last update: 2023-09-28 07:12:44+09:00
Problem: https://atcoder.jp/contests/abc307/tasks/abc307_e

Depends on

Code

#define PROBLEM "https://atcoder.jp/contests/abc307/tasks/abc307_e"

#include "../../Src/Template/TypeAlias.hpp"
#include "../../Src/Number/ModInt.hpp"

#include <iostream>
#include <array>

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

int main() {
    u32 n, m; std::cin >> n >> m;
    std::array<m32, 2> dp{ m32{m}, m32{} }; 
    for (u32 _{} ; _ < n - 1 ; _++) {
        std::array<m32, 2> nxt;
        nxt[0] = dp[1];
        nxt[1] = dp[0] * m32{m - 1} + dp[1] * m32{m - 2};
        dp = std::move(nxt);
    }
    std::cout << dp[1] << std::endl;
}

#line 1 "Test/AtCoder/abc307_e.test.cpp"
#define PROBLEM "https://atcoder.jp/contests/abc307/tasks/abc307_e"

#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/Number/ModInt.hpp"

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

#include <type_traits>
#include <iostream>
#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 5 "Test/AtCoder/abc307_e.test.cpp"

#line 7 "Test/AtCoder/abc307_e.test.cpp"
#include <array>

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

int main() {
    u32 n, m; std::cin >> n >> m;
    std::array<m32, 2> dp{ m32{m}, m32{} }; 
    for (u32 _{} ; _ < n - 1 ; _++) {
        std::array<m32, 2> nxt;
        nxt[0] = dp[1];
        nxt[1] = dp[0] * m32{m - 1} + dp[1] * m32{m - 2};
        dp = std::move(nxt);
    }
    std::cout << dp[1] << std::endl;
}