結果
問題 | No.1100 Boxes |
ユーザー |
|
提出日時 | 2020-06-26 21:59:32 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 143 ms / 2,000 ms |
コード長 | 16,346 bytes |
コンパイル時間 | 7,738 ms |
コンパイル使用メモリ | 211,524 KB |
最終ジャッジ日時 | 2025-01-11 11:25:29 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 36 |
ソースコード
#include <bits/stdc++.h>using ll = long long;using uint = unsigned int;using ull = unsigned long long;using ld = long double;template<typename T>using max_heap = std::priority_queue<T>;template<typename T>using min_heap = std::priority_queue<T, std::vector<T>, std::greater<T>>;constexpr int popcount(const ull v) { return v ? __builtin_popcountll(v) : 0; }constexpr int log2p1(const ull v) { return v ? 64 - __builtin_clzll(v) : 0; }constexpr int lsbp1(const ull v) { return __builtin_ffsll(v); }constexpr int clog(const ull v) { return v ? log2p1(v - 1) : 0; }constexpr ull ceil2(const ull v) { return 1ULL << clog(v); }constexpr ull floor2(const ull v) { return v ? (1ULL << (log2p1(v) - 1)) : 0ULL; }constexpr bool btest(const ull mask, const int ind) { return (mask >> ind) & 1ULL; }template<typename T> void bset(T& mask, const int ind) { mask |= ((T)1 << ind); }template<typename T> void breset(T& mask, const int ind) { mask &= ~((T)1 << ind); }template<typename T> void bflip(T& mask, const int ind) { mask ^= ((T)1 << ind); }template<typename T> void bset(T& mask, const int ind, const bool b) { (b ? bset(mask, ind) : breset(mask, ind)); }template<typename T> bool chmin(T& a, const T& b) { return (a > b ? a = b, true : false); }template<typename T> bool chmax(T& a, const T& b) { return (a < b ? a = b, true : false); }template<typename T> constexpr T inf_v = std::numeric_limits<T>::max() / 4;template<typename Real> constexpr Real pi_v = Real{3.141592653589793238462643383279502884};constexpr ull TEN(const int n) { return n == 0 ? 1ULL : TEN(n - 1) * 10ULL; }template<typename F> struct fix : F{fix(F&& f) : F{std::forward<F>(f)} {}template<typename... Args> auto operator()(Args&&... args) const { return F::operator()(*this, std::forward<Args>(args)...); }};class printer{public:printer(std::ostream& os_ = std::cout) : os{os_} {}template<typename T> int operator()(const T& v) { return os << v, 0; }template<typename T> int operator()(const std::vector<T>& vs){for (int i = 0; i < (int)vs.size(); i++) { os << (i ? " " : ""), this->operator()(vs[i]); }return 0;}template<typename T> int operator()(const std::vector<std::vector<T>>& vss){for (int i = 0; i < (int)vss.size(); i++) { os << (0 <= i or i + 1 < (int)vss.size() ? "\n" : ""), this->operator()(vss[i]); }return 0;}template<typename T, typename... Args> int operator()(const T& v, const Args&... args) { return this->operator()(v), os << ' ', this->operator()(args...), 0; }template<typename... Args> int ln(const Args&... args) { return this->operator()(args...), os << '\n', 0; }template<typename... Args> int el(const Args&... args) { return this->operator()(args...), os << std::endl, 0; }template<typename... Args> int fmt(const std::string& s, const Args&... args) { return rec(s, 0, args...); }private:int rec(const std::string& s, int index) { return os << s.substr(index, s.size()), 0; }template<typename T, typename... Args> int rec(const std::string& s, int index, const T& v, const Args&... args) { return index == s.size() ? 0 :s[index] == '%' ? (this->operator()(v), rec(s, index + 1, args...)) : (os << s[index], rec(s, index + 1, v, args...)); }std::ostream& os;};printer out;template<typename T, typename F> std::vector<T> generated(const int n, F f){std::vector<T> ans(n);return std::generate(ans.begin(), ans.end(), f), ans;}std::vector<int> ioted(const int n, const int offset = 0){std::vector<int> ans(n);return std::iota(ans.begin(), ans.end(), offset), ans;}template<typename Vs> Vs reversed(const Vs& vs){auto ans = vs;return std::reverse(ans.begin(), ans.end()), ans;}template<typename T, typename F = std::less<T>> std::vector<T> sorted(const std::vector<T>& vs, F comp = F{}){auto ans = vs;return std::sort(ans.begin(), ans.end(), comp), ans;}template<typename F> std::vector<int> sorted_iota(const int n, F comp = F{}, const int offset = 0) { return sorted(ioted(n, offset), comp); }class scanner{public:scanner(std::istream& is_ = std::cin) : is{is_} { is.tie(nullptr), std::ios::sync_with_stdio(false); }template<typename T> T val(){static T v;return is >> v, v;}template<typename T> T val(const T offset) { return val<T>() - offset; }template<typename T> std::vector<T> vec(const int n){return generated<T>(n, [&] { return val<T>(); });}template<typename T> std::vector<T> vec(const int n, const T offset){return generated<T>(n, [&] { return val<T>(offset); });}template<typename T> std::vector<std::vector<T>> vvec(const int n0, const int n1){return generated<std::vector<T>>(n0, [&] { return vec<T>(n1); });}template<typename T> std::vector<std::vector<T>> vvec(const int n0, const int n1, const T offset){return generated<std::vector<T>>(n0, [&] { return vec<T>(n1, offset); });}template<typename... Args> auto tup() { return std::tuple<std::decay_t<Args>...>{val<Args>()...}; }template<typename... Args> auto tup(const Args&... offsets) { return std::tuple<std::decay_t<Args>...>{val<Args>(offsets)...}; }private:std::istream& is;};scanner in;# define SHOW(...) static_cast<void>(0)template<typename T, int n, int i = 0>auto make_v(int const (&szs)[n], const T x = T{}){if constexpr (i == n) {return x;} else {return std::vector(szs[i], make_v<T, n, i + 1>(szs, x));}}template<typename T>constexpr std::pair<T, T> extgcd(const T a, const T b){if (b == 0) { return std::pair<T, T>{1, 0}; }const auto g = std::gcd(a, b), da = std::abs(b) / g;const auto p = extgcd(b, a % b);const auto x = (da + p.second % da) % da, y = (g - a * x) / b;return {x, y};}template<typename T> constexpr T inverse(const T a, const T mod) { return extgcd(a, mod).first; }template<uint mod_value, bool dynamic = false>class modint_base{public:template<typename UInt = uint>static std::enable_if_t<dynamic, const UInt> mod() { return mod_ref(); }template<typename UInt = uint>static constexpr std::enable_if_t<not dynamic, const UInt> mod() { return mod_value; }template<typename UInt = uint>static void set_mod(const std::enable_if_t<dynamic, const UInt> mod) { mod_ref() = mod, inv_ref() = {1, 1}; }modint_base() : v{0} {}modint_base(const ll val) : v{norm(static_cast<uint>(val % static_cast<ll>(mod()) + static_cast<ll>(mod())))} {}modint_base(const modint_base& n) : v{n()} {}explicit operator bool() const { return v != 0; }explicit operator int() const { return v; }explicit operator uint() const { return v; }explicit operator ll() const { return v; }explicit operator ull() const { return v; }bool operator!() const { return not static_cast<bool>(*this); }modint_base& operator=(const modint_base& m) { return v = m(), (*this); }modint_base& operator=(const ll val) { return v = norm(uint(val % static_cast<ll>(mod()) + static_cast<ll>(mod()))), (*this); }friend modint_base operator+(const modint_base& m) { return m; }friend modint_base operator-(const modint_base& m) { return make(norm(mod() - m.v)); }friend modint_base operator+(const modint_base& m1, const modint_base& m2) { return make(norm(m1.v + m2.v)); }friend modint_base operator-(const modint_base& m1, const modint_base& m2) { return make(norm(m1.v + mod() - m2.v)); }friend modint_base operator*(const modint_base& m1, const modint_base& m2) { return make(static_cast<uint>(static_cast<ll>(m1.v) * static_cast<ll>(m2.v) % static_cast<ll>(mod()))); }friend modint_base operator/(const modint_base& m1, const modint_base& m2) { return m1 * inv(m2.v); }friend modint_base operator+(const modint_base& m, const ll val) { return modint_base{static_cast<ll>(m.v) + val}; }friend modint_base operator-(const modint_base& m, const ll val) { return modint_base{static_cast<ll>(m.v) - val}; }friend modint_base operator*(const modint_base& m, const ll val) { return modint_base{static_cast<ll>(m.v) * (val % static_cast<ll>(mod()))}; }friend modint_base operator/(const modint_base& m, const ll val) { return modint_base{static_cast<ll>(m.v) * inv(val)}; }friend modint_base operator+(const ll val, const modint_base& m) { return modint_base{static_cast<ll>(m.v) + val}; }friend modint_base operator-(const ll val, const modint_base& m) { return modint_base{-static_cast<ll>(m.v) + val}; }friend modint_base operator*(const ll val, const modint_base& m) { return modint_base{static_cast<ll>(m.v) * (val % static_cast<ll>(mod()))}; }friend modint_base operator/(const ll val, const modint_base& m) { return modint_base{val * inv(static_cast<ll>(m.v))}; }friend modint_base& operator+=(modint_base& m1, const modint_base& m2) { return m1 = m1 + m2; }friend modint_base& operator-=(modint_base& m1, const modint_base& m2) { return m1 = m1 - m2; }friend modint_base& operator*=(modint_base& m1, const modint_base& m2) { return m1 = m1 * m2; }friend modint_base& operator/=(modint_base& m1, const modint_base& m2) { return m1 = m1 / m2; }friend modint_base& operator+=(modint_base& m, const ll val) { return m = m + val; }friend modint_base& operator-=(modint_base& m, const ll val) { return m = m - val; }friend modint_base& operator*=(modint_base& m, const ll val) { return m = m * val; }friend modint_base& operator/=(modint_base& m, const ll val) { return m = m / val; }friend modint_base operator^(const modint_base& m, const ll n) { return power(m.v, n); }friend modint_base& operator^=(modint_base& m, const ll n) { return m = m ^ n; }friend bool operator==(const modint_base& m1, const modint_base& m2) { return m1.v == m2.v; }friend bool operator!=(const modint_base& m1, const modint_base& m2) { return not(m1 == m2); }friend bool operator==(const modint_base& m, const ll val) { return m.v == norm(static_cast<uint>(static_cast<ll>(mod()) + val % static_cast<ll>(mod()))); }friend bool operator!=(const modint_base& m, const ll val) { return not(m == val); }friend bool operator==(const ll val, const modint_base& m) { return m.v == norm(static_cast<uint>(static_cast<ll>(mod()) + val % static_cast<ll>(mod()))); }friend bool operator!=(const ll val, const modint_base& m) { return not(m == val); }friend std::istream& operator>>(std::istream& is, modint_base& m){ll v;return is >> v, m = v, is;}friend std::ostream& operator<<(std::ostream& os, const modint_base& m) { return os << m(); }uint operator()() const { return v; }static modint_base fact(const int n){auto& fact_ = fact_ref();if (n < (int)fact_.size()) { return fact_[n]; }for (int i = (int)fact_.size(); i <= n; i++) { fact_.push_back(fact_.back() * i); }return fact_.back();}static modint_base inv_fact(const int n){auto& inv_fact_ = inv_fact_ref();if (n < (int)inv_fact_.size()) { return inv_fact_[n]; }for (int i = inv_fact_.size(); i <= n; i++) { inv_fact_.push_back(inv_fact_.back() * modint_base::small_inv(i)); }return inv_fact_.back();}static modint_base perm(const int n, const int k) { return k > n ? modint_base{0} : fact(n) * inv_fact(n - k); }static modint_base comb(const int n, const int k) { return k > n ? modint_base{0} : fact(n) * inv_fact(n - k) * inv_fact(k); }std::pair<ll, ll> quad() const{const auto ans = quad_r(v, mod());ll x = std::get<0>(ans), y = std::get<1>(ans);if (y < 0) { x = -x, y = -y; }return {x, y};}private:static std::tuple<ll, ll, ll> quad_r(const ll r, const ll p) // r = x/y (mod p), (x,y,z) s.t. x=yr+pz{if (std::abs(r) <= 1000) { return {r, 1, 0}; }ll nr = p % r, q = p / r;if (nr * 2LL >= r) { nr -= r, q++; }if (nr * 2LL <= -r) { nr += r, q--; }const auto sub = quad_r(nr, r);const ll x = std::get<0>(sub), z = std::get<1>(sub), y = std::get<2>(sub);return {x, y - q * z, z};}template<typename UInt = uint>static std::enable_if_t<dynamic, UInt&> mod_ref(){static UInt mod = 0;return mod;}static uint norm(const uint x) { return x < mod() ? x : x - mod(); }static modint_base make(const uint x){modint_base m;return m.v = x, m;}static modint_base power(modint_base x, ull n){modint_base ans = 1;for (; n; n >>= 1, x *= x) {if (n & 1) { ans *= x; }}return ans;}static modint_base small_inv(const int n){auto& inv_ = inv_ref();if (n < (int)inv_.size()) { return inv_[n]; }for (int i = inv_.size(); i <= n; i++) { inv_.push_back(-inv_[modint_base::mod() % i] * (modint_base::mod() / i)); }return inv_.back();}static modint_base inv(const ll v) { return v <= 2000000 ? small_inv(static_cast<int>(v)) : modint_base{inverse(v, static_cast<ll>(mod()))}; }static std::vector<modint_base>& inv_ref(){static std::vector<modint_base> inv_{1, 1};return inv_;}static std::vector<modint_base>& fact_ref(){static std::vector<modint_base> fact_{1, 1};return fact_;}static std::vector<modint_base>& inv_fact_ref(){static std::vector<modint_base> inv_fact_{1, 1};return inv_fact_;}uint v;};template<uint mod>using modint = modint_base<mod, false>;template<uint id>using dynamic_modint = modint_base<id, true>;template<uint mod = 998244353, uint root = 3>class ntt{private:static constexpr int depth = 30;static void transform(std::vector<modint<mod>>& a, const int lg, const bool rev){const int N = a.size();static std::vector<modint<mod>> R[depth];if (R[lg].empty()) {R[lg].reserve(N), R[lg].resize(N, modint<mod>(1));const modint<mod> r = modint<mod>(root) ^ ((mod - 1) / N);for (int i = 1; i < N; i++) { R[lg][i] = R[lg][i - 1] * r; }}std::vector<modint<mod>> tmp(N);for (int w = (N >> 1); w > 0; w >>= 1) {for (int y = 0; y < (N >> 1); y += w) {const modint<mod> r = rev ? R[lg][y == 0 ? 0 : N - y] : R[lg][y];for (int x = 0; x < w; x++) {const auto u = a[y << 1 | x], v = a[y << 1 | x | w]() * r;tmp[y | x] = u + v, tmp[y | x | (N >> 1)] = u - v;}}std::swap(tmp, a);}if (rev) {for (int i = 0; i < N; i++) { a[i] /= modint<mod>(N); }}}public:ntt() = delete;static std::vector<modint<mod>> convolute(const std::vector<modint<mod>>& a, const std::vector<modint<mod>>& b){const int need = a.size() + b.size() - 1, lg = clog(need), sz = 1UL << lg;std::vector<modint<mod>> A(sz, 0), B(sz, 0);for (int i = 0; i < (int)a.size(); i++) { A[i] = a[i](); }for (int i = 0; i < (int)b.size(); i++) { B[i] = b[i](); }transform(A, lg, false), transform(B, lg, false);for (int i = 0; i < sz; i++) { A[i] *= B[i]; }transform(A, lg, true);std::vector<modint<mod>> ans(need);for (int i = 0; i < need; i++) { ans[i] = int(A[i]()); }return ans;}};int main(){using mint = modint<998244353>;const auto [N, K] = in.tup<int, int>();std::vector<mint> c1(K + 1, 0);std::vector<mint> c2(K + 1, 0);for (int i = 0; i <= K; i++) {c1[i] = (mint(i) ^ N) * (i % 2 == 0 ? 1 : -1) * mint::inv_fact(i);c2[i] = mint::inv_fact(i);}SHOW(c2);auto c3 = ntt<998244353, 3>::convolute(c1, c2);c3.resize(K + 1);for (int i = 1; i <= K; i += 2) { c3[i] = 0; }SHOW(c3);auto c4 = ntt<998244353, 3>::convolute(c3, c2);SHOW(c4);const auto even = c4[K] * mint::fact(K);SHOW(even);out.ln(K % 2 == 1 ? even : (mint(K) ^ N) - even);return 0;}