結果
| 問題 |
No.2351 Butterfly in Summer
|
| コンテスト | |
| ユーザー |
 KoD
|
| 提出日時 | 2023-06-16 21:23:55 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 2,000 ms |
| コード長 | 9,568 bytes |
| コンパイル時間 | 1,281 ms |
| コンパイル使用メモリ | 131,252 KB |
| 最終ジャッジ日時 | 2025-02-14 04:16:02 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 21 |
ソースコード
// #define MULTEST
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <type_traits>
#include <utility>
#include <variant>
#include <vector>
namespace kod {
namespace util {
template <class F> class fixed_point : private F {
constexpr fixed_point(F&& f) noexcept : F(std::forward<F>(f)) {}
template <class G> friend constexpr decltype(auto) make_fixed(G&&) noexcept;
public:
template <class... Args> constexpr decltype(auto) operator()(Args&&... args) const noexcept {
return F::operator()(*this, std::forward<Args>(args)...);
}
};
template <class G> [[nodiscard]] constexpr decltype(auto) make_fixed(G&& g) noexcept {
using F = std::decay_t<G>;
return fixed_point<F>(std::forward<F>(g));
}
} // namespace util
} // namespace kod
namespace kod {
namespace util {
class forward_loop {
int x, y;
constexpr forward_loop(int x, int y) noexcept : x(x), y(y) {}
friend constexpr forward_loop rep(int, int) noexcept;
friend constexpr forward_loop rep(int) noexcept;
public:
constexpr forward_loop begin() const noexcept { return *this; }
constexpr std::monostate end() const noexcept { return {}; }
constexpr bool operator!=(std::monostate) const noexcept { return x < y; }
constexpr void operator++() const noexcept {}
constexpr int operator*() noexcept { return x++; }
};
[[nodiscard]] constexpr forward_loop rep(int l, int r) noexcept { return forward_loop(l, r); }
[[nodiscard]] constexpr forward_loop rep(int n) noexcept { return forward_loop(0, n); }
class backward_loop {
int x, y;
constexpr backward_loop(int x, int y) noexcept : x(x), y(y) {}
friend constexpr backward_loop revrep(int, int) noexcept;
friend constexpr backward_loop revrep(int) noexcept;
public:
constexpr backward_loop begin() const noexcept { return *this; }
constexpr std::monostate end() const noexcept { return {}; }
constexpr bool operator!=(std::monostate) const noexcept { return x > y; }
constexpr void operator++() const noexcept {}
constexpr int operator*() noexcept { return --x; }
};
[[nodiscard]] constexpr backward_loop revrep(int l, int r) noexcept { return backward_loop(r, l); }
[[nodiscard]] constexpr backward_loop revrep(int n) noexcept { return backward_loop(n, 0); }
template <class F> constexpr void repeat(int n, const F& f) noexcept {
assert(n >= 0);
while (n--) f();
}
} // namespace util
} // namespace kod
namespace kod {
namespace util {
namespace stdio_impl {
template <class T> T scan() {
T x;
std::cin >> x;
return x;
}
struct scan_any {
template <class T> operator T() const { return scan<T>(); }
};
} // namespace stdio_impl
template <class T = void> decltype(auto) scan() {
if constexpr (std::is_same_v<T, void>) return stdio_impl::scan_any{};
else return stdio_impl::scan<T>();
}
template <class T, std::size_t N> std::array<T, N> scan_arr() {
std::array<T, N> a;
for (auto& x : a) x = scan<T>();
return a;
}
template <class T> std::vector<T> scan_vec(int n) {
if (n == -1) n = scan<int>();
assert(n >= 0);
std::vector<T> v;
v.reserve(n);
while (n--) v.push_back(scan<T>());
return v;
}
void flush() { std::cout << std::flush; }
void print() {}
template <class T, class... Args> void print(const T& x, const Args&... args) {
std::cout << x;
if (sizeof...(args) != 0) std::cout << ' ';
print(args...);
}
template <class... Args> void println(const Args&... args) {
print(args...);
std::cout << '\n';
}
template <class C> void print_seq(const C& c, const char* sep = " ", const char* end = "\n") {
bool f = false;
for (const auto& x : c) {
if (f) std::cout << sep;
else f = true;
std::cout << x;
}
std::cout << end;
}
} // namespace util
} // namespace kod
namespace kod {
namespace sol {
using ll = long long;
using uint = unsigned;
using ull = unsigned long long;
using std::array;
using std::pair;
using std::string;
using std::tuple;
using std::vector;
using namespace util;
constexpr int inf = std::numeric_limits<int>::max() / 2;
constexpr ll infll = std::numeric_limits<ll>::max() / 2;
constexpr ll floor_div(ll x, ll y) noexcept {
assert(y != 0);
return x / y - ((x ^ y) < 0 && x % y != 0);
}
constexpr ll ceil_div(ll x, ll y) noexcept {
assert(y != 0);
return x / y + ((x ^ y) >= 0 && x % y != 0);
}
template <class T> constexpr bool setmin(T& lhs, const T& rhs) noexcept {
if (lhs > rhs) {
lhs = rhs;
return true;
}
return false;
}
template <class T> constexpr bool setmax(T& lhs, const T& rhs) noexcept {
if (lhs < rhs) {
lhs = rhs;
return true;
}
return false;
}
void run();
} // namespace sol
} // namespace kod
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout << std::fixed << std::setprecision(20);
int cases = 1;
#ifdef MULTEST
std::cin >> cases;
#endif
while (cases--) kod::sol::run();
return 0;
}
#ifdef KOD_LOCAL
#define OJ_LOCAL(a, b) b
#include <kodlib/misc/debug>
#else
#define OJ_LOCAL(a, b) a
#define DBG(...)
#define SHOW(...)
#endif
namespace kod {
namespace mod {
namespace finite_field_impl {
constexpr bool is_valid_mod(unsigned m) noexcept {
if (m <= 1 || (1u << 31) <= m) return false;
for (unsigned i = 2; i * i <= m; ++i) {
if (m % i == 0) return false;
}
return true;
}
constexpr long long rem_euclid(long long x, long long y) noexcept {
if (x >= 0) return x < y ? x : x % y;
if (x >= -y) return x + y;
return (x %= y) == 0 ? 0 : x + y;
}
template <unsigned MOD, std::enable_if_t<is_valid_mod(MOD)>* = nullptr> class finite_field {
public:
constexpr finite_field() noexcept : v(0) {}
constexpr finite_field(long long x) noexcept : v(rem_euclid(x, MOD)) {}
constexpr finite_field& operator+=(const finite_field& x) noexcept {
v += x.v;
if (v >= MOD) v -= MOD;
return *this;
}
constexpr finite_field& operator-=(const finite_field& x) noexcept {
if (v < x.v) v += MOD;
v -= x.v;
return *this;
}
constexpr finite_field& operator*=(const finite_field& x) noexcept {
v = (unsigned long long)v * x.v % MOD;
return *this;
}
constexpr finite_field& operator/=(const finite_field& x) noexcept { return *this *= x.inv(); }
constexpr finite_field operator+() const noexcept { return *this; }
constexpr finite_field operator-() const noexcept { return raw(v == 0 ? 0 : MOD - v); }
friend constexpr finite_field operator+(finite_field x, const finite_field& y) noexcept { return x += y; }
friend constexpr finite_field operator-(finite_field x, const finite_field& y) noexcept { return x -= y; }
friend constexpr finite_field operator*(finite_field x, const finite_field& y) noexcept { return x *= y; }
friend constexpr finite_field operator/(finite_field x, const finite_field& y) noexcept { return x /= y; }
friend constexpr bool operator==(const finite_field& x, const finite_field& y) noexcept { return x.v == y.v; }
friend constexpr bool operator!=(const finite_field& x, const finite_field& y) noexcept { return x.v != y.v; }
friend std::ostream& operator<<(std::ostream& s, const finite_field& x) noexcept { return s << x.v; }
constexpr unsigned val() const noexcept { return v; }
constexpr finite_field inv() const noexcept { return pow(MOD - 2); }
constexpr finite_field pow(long long e) const noexcept {
if (v == 0) {
assert(e >= 0);
return raw(e == 0);
}
unsigned long long x = 1, y = v;
for (e = rem_euclid(e, MOD - 1); e > 0; e >>= 1) {
if (e & 1) x = x * y % MOD;
y = y * y % MOD;
}
return raw(x);
}
static constexpr unsigned mod() noexcept { return MOD; }
static constexpr finite_field raw(unsigned x) noexcept {
finite_field ret;
ret.v = x;
return ret;
}
static finite_field fact(int n) noexcept {
assert(n >= 0);
static std::vector v = {raw(1)};
for (int i = (int)v.size(); i <= n; ++i) v.push_back(v.back() * finite_field(i));
return v[n];
}
static finite_field inv(int n) noexcept {
assert(n >= 1);
static std::vector v = {raw(0), raw(1)};
for (int i = (int)v.size(); i <= n; ++i) v.push_back(-raw(mod() / i) * v[mod() % i]);
return v[n];
}
static finite_field ifact(int n) noexcept {
assert(n >= 0);
static std::vector v = {raw(1)};
for (int i = (int)v.size(); i <= n; ++i) v.push_back(v.back() * inv(i));
return v[n];
}
static finite_field factpow(int n, int d) noexcept { return 0 <= d && d <= n ? fact(n) * ifact(n - d) : raw(0); }
static finite_field binom(int n, int d) noexcept { return 0 <= d && d <= n ? factpow(n, d) * ifact(d) : raw(0); }
static finite_field nbinom(int n, int d) noexcept {
return n >= 0 && d >= 0 ? (n == 0 ? raw(d == 0) : binom(n + d - 1, d)) : raw(0);
}
private:
unsigned v;
};
} // namespace finite_field_impl
using finite_field_impl::finite_field;
using F_998244353 = finite_field<998244353>;
using F_1000000007 = finite_field<1000000007>;
} // namespace mod
} // namespace kod
namespace kod {
namespace sol {
using Fp = mod::F_998244353;
void run() {
const int n = scan();
const int k = scan();
println(Fp(n) * Fp(k) * Fp(k - 1) / Fp(k).pow(n));
}
} // namespace sol
} // namespace kod