結果

問題 No.1302 Random Tree Score
ユーザー KoD
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0