結果
問題 | No.1302 Random Tree Score |
ユーザー |
![]() |
提出日時 | 2020-11-27 22:35:57 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 12 ms / 3,000 ms |
コード長 | 7,253 bytes |
コンパイル時間 | 910 ms |
コンパイル使用メモリ | 76,984 KB |
最終ジャッジ日時 | 2025-01-16 07:59:09 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 14 |
ソースコード
#line 1 "main.cpp"/*** @title Template*/#include <iostream>#include <algorithm>#include <utility>#include <numeric>#include <vector>#include <array>#include <cassert>#line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/other/range.cpp"#line 4 "/Users/kodamankod/Desktop/cpp_programming/Library/other/range.cpp"class range {struct iter {std::size_t itr;constexpr iter(std::size_t pos) noexcept: itr(pos) { }constexpr void operator ++ () noexcept { ++itr; }constexpr bool operator != (iter other) const noexcept { return itr != other.itr; }constexpr std::size_t operator * () const noexcept { return itr; }};struct reviter {std::size_t itr;constexpr reviter(std::size_t pos) noexcept: itr(pos) { }constexpr void operator ++ () noexcept { --itr; }constexpr bool operator != (reviter other) const noexcept { return itr != other.itr; }constexpr std::size_t operator * () const noexcept { return itr; }};const iter first, last;public:constexpr range(std::size_t first, std::size_t last) noexcept: first(first), last(std::max(first, last)) { }constexpr iter begin() const noexcept { return first; }constexpr iter end() const noexcept { return last; }constexpr reviter rbegin() const noexcept { return reviter(*last - 1); }constexpr reviter rend() const noexcept { return reviter(*first - 1); }};/*** @title Range*/#line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/algebraic/modular.cpp"#line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/algebraic/mod_inv.cpp"#line 4 "/Users/kodamankod/Desktop/cpp_programming/Library/algebraic/mod_inv.cpp"#include <cstdint>constexpr std::pair<int64_t, int64_t> mod_inv(int64_t a, int64_t b) {if ((a %= b) == 0) return { b, 0 };int64_t s = b, t = (a < 0 ? a + b : a);int64_t m0 = 0, m1 = 1, tmp = 0;while (t > 0) {const auto u = s / t;s -= t * u; m0 -= m1 * u;tmp = s; s = t; t = tmp; tmp = m0; m0 = m1; m1 = tmp;}return { s, (m0 < 0 ? m0 + b / s : m0) };}/*** @title Extended GCD*/#line 4 "/Users/kodamankod/Desktop/cpp_programming/Library/algebraic/modular.cpp"#line 8 "/Users/kodamankod/Desktop/cpp_programming/Library/algebraic/modular.cpp"#include <type_traits>template <class Modulus>class modular {public:using value_type = uint32_t;using cover_type = uint64_t;static constexpr uint32_t mod() { return Modulus::mod(); }template <class T>static constexpr value_type normalize(T value_) noexcept {if (value_ < 0) {value_ = -value_;value_ %= mod();if (value_ == 0) return 0;return mod() - value_;}return value_ % mod();}private:value_type value;template <bool IsPrime, std::enable_if_t<IsPrime>* = nullptr>constexpr modular inverse_helper() const noexcept { return power(*this, mod() - 2); }template <bool IsPrime, std::enable_if_t<!IsPrime>* = nullptr>constexpr modular inverse_helper() const noexcept {const auto tmp = mod_inv(value, mod());assert(tmp.first == 1);return modular(tmp.second);}public:constexpr modular() noexcept : value(0) { }template <class T>explicit constexpr modular(T value_) noexcept : value(normalize(value_)) { }template <class T>explicit constexpr operator T() const noexcept { return static_cast<T>(value); }constexpr value_type get() const noexcept { return value; }constexpr value_type &extract() noexcept { return value; }constexpr modular operator - () const noexcept { return modular(mod() - value); }constexpr modular operator ~ () const noexcept { return inverse(*this); }constexpr modular operator + (const modular &rhs) const noexcept { return modular(*this) += rhs; }constexpr modular& operator += (const modular &rhs) noexcept {if ((value += rhs.value) >= mod()) value -= mod();return *this;}constexpr modular operator - (const modular &rhs) const noexcept { return modular(*this) -= rhs; }constexpr modular& operator -= (const modular &rhs) noexcept {if ((value += mod() - rhs.value) >= mod()) value -= mod();return *this;}constexpr modular operator * (const modular &rhs) const noexcept { return modular(*this) *= rhs; }constexpr modular& operator *= (const modular &rhs) noexcept {value = (cover_type) value * rhs.value % mod();return *this;}constexpr modular operator / (const modular &rhs) const noexcept { return modular(*this) /= rhs; }constexpr modular& operator /= (const modular &rhs) noexcept { return (*this) *= inverse(rhs); }constexpr bool zero() const noexcept { return value == 0; }constexpr bool operator == (const modular &rhs) const noexcept { return value == rhs.value; }constexpr bool operator != (const modular &rhs) const noexcept { return value != rhs.value; }friend std::ostream& operator << (std::ostream &stream, const modular &rhs) { return stream << rhs.value; }friend constexpr modular inverse(const modular &val) noexcept { return val.inverse_helper<Modulus::is_prime>(); }friend constexpr modular power(modular val, cover_type exp) noexcept {modular res(1);for (; exp > 0; exp >>= 1, val *= val) if (exp & 1) res *= val;return res;}};template <uint32_t Mod, bool IsPrime = true>struct static_modulus {static constexpr uint32_t mod() noexcept { return Mod; }static constexpr bool is_prime = IsPrime;};template <uint32_t Id = 0, bool IsPrime = false>struct dynamic_modulus {static uint32_t &mod() noexcept { static uint32_t val = 0; return val; }static constexpr bool is_prime = IsPrime;};template <uint32_t Mod, bool IsPrime = true>using mint32_t = modular<static_modulus<Mod, IsPrime>>;using rmint32_t = modular<dynamic_modulus<>>;/** @title Modint*/#line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/algebraic/factorials.cpp"#include <cstddef>#line 6 "/Users/kodamankod/Desktop/cpp_programming/Library/algebraic/factorials.cpp"template <class T, size_t N>class factorials {public:using value_type = T;public:std::array<value_type, N + 1> fact{};std::array<value_type, N + 1> fact_inv{};factorials() {fact.front() = value_type(1);for (size_t i = 1; i <= N; ++i) {fact[i] = fact[i - 1] * value_type(i);}fact_inv.back() = value_type(1) / fact.back();for (size_t i = N; i > 0; --i) {fact_inv[i - 1] = fact_inv[i] * value_type(i);}}value_type operator () (size_t n, size_t r) const {assert(n <= N);assert(n >= r);return fact[n] * fact_inv[n - r] * fact_inv[r];}};/*** @title Factorial*/#line 17 "main.cpp"using i32 = std::int32_t;using i64 = std::int64_t;using u32 = std::uint32_t;using u64 = std::uint64_t;using isize = std::ptrdiff_t;using usize = std::size_t;constexpr i32 inf32 = (i32(1) << 30) - 1;constexpr i64 inf64 = (i64(1) << 62) - 1;using Fp = mint32_t<998244353>;factorials<Fp, 100000> fact;int main() {usize N;std::cin >> N;Fp ans;for (auto i: range(0, N - 1)) {ans += fact.fact[N - 2] * fact.fact_inv[(N - 2) - i] * power(Fp(N), (N - 2) - i) * fact(N, i);}std::cout << ans / power(Fp(N), N - 2) << '\n';return 0;}