結果
問題 | No.895 MESE |
ユーザー | jell |
提出日時 | 2020-06-06 00:03:54 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 16,699 bytes |
コンパイル時間 | 1,590 ms |
コンパイル使用メモリ | 145,324 KB |
実行使用メモリ | 9,600 KB |
最終ジャッジ日時 | 2024-05-10 00:34:57 |
合計ジャッジ時間 | 3,144 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 18 ms
9,472 KB |
testcase_01 | AC | 18 ms
9,600 KB |
testcase_02 | WA | - |
testcase_03 | AC | 19 ms
9,596 KB |
testcase_04 | AC | 19 ms
9,508 KB |
testcase_05 | AC | 17 ms
9,600 KB |
testcase_06 | WA | - |
testcase_07 | AC | 20 ms
9,564 KB |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | WA | - |
ソースコード
#ifdef stderr_path #define LOCAL #endif #ifdef LOCAL #define _GLIBCXX_DEBUG #else #pragma GCC optimize("Ofast") #endif #include <algorithm> #include <bitset> #include <cassert> #include <chrono> #include <complex> #include <cstring> #include <deque> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <random> #include <set> #include <stack> #include <unordered_map> #include <unordered_set> // #define NDEBUG #define debug_stream std::cerr #define iostream_untie true #define __precision__ 10 #define all(v) std::begin(v), std::end(v) #define rall(v) std::rbegin(v), std::rend(v) #define __odd(n) ((n)&1) #define __even(n) (not __odd(n)) #define __popcount(n) __builtin_popcountll(n) #define __clz32(n) __builtin_clz(n) #define __clz64(n) __builtin_clzll(n) #define __ctz32(n) __builtin_ctz(n) #define __ctz64(n) __builtin_ctzll(n) using i64 = int_fast64_t; using pii = std::pair<int, int>; using pll = std::pair<int_fast64_t, int_fast64_t>; template <class T> using heap = std::priority_queue<T>; template <class T> using minheap = std::priority_queue<T, std::vector<T>, std::greater<T>>; template <class T> constexpr T inf = std::numeric_limits<T>::max() / T(2) - T(1123456); namespace execution { std::chrono::system_clock::time_point start_time, end_time; void print_elapsed_time() { end_time = std::chrono::system_clock::now(); std::cerr << "\n----- Exec time : "; std::cerr << std::chrono::duration_cast<std::chrono::milliseconds>( end_time - start_time) .count(); std::cerr << " ms -----\n\n"; } struct setupper { setupper() { if(iostream_untie) { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); } std::cout << std::fixed << std::setprecision(__precision__); #ifdef stderr_path if(freopen(stderr_path, "a", stderr)) { std::cerr << std::fixed << std::setprecision(__precision__); } #endif #ifdef stdout_path if(not freopen(stdout_path, "w", stdout)) { freopen("CON", "w", stdout); std::cerr << "Failed to open the stdout file\n\n"; } std::cout << ""; #endif #ifdef stdin_path if(not freopen(stdin_path, "r", stdin)) { freopen("CON", "r", stdin); std::cerr << "Failed to open the stdin file\n\n"; } #endif #ifdef LOCAL std::cerr << "----- stderr at LOCAL -----\n\n"; atexit(print_elapsed_time); start_time = std::chrono::system_clock::now(); #else fclose(stderr); #endif } } __setupper; } // namespace execution class myclock_t { std::chrono::system_clock::time_point built_pt, last_pt; int built_ln, last_ln; std::string built_func, last_func; bool is_built; public: explicit myclock_t() : is_built(false) { } void build(int crt_ln, const std::string &crt_func) { is_built = true; last_pt = built_pt = std::chrono::system_clock::now(); last_ln = built_ln = crt_ln, last_func = built_func = crt_func; } void set(int crt_ln, const std::string &crt_func) { if(is_built) { last_pt = std::chrono::system_clock::now(); last_ln = crt_ln, last_func = crt_func; } else { debug_stream << "[ " << crt_ln << " : " << crt_func << " ] " << "myclock_t::set failed (yet to be built!)\n"; } } void get(int crt_ln, const std::string &crt_func) { if(is_built) { std::chrono::system_clock::time_point crt_pt( std::chrono::system_clock::now()); int64_t diff = std::chrono::duration_cast<std::chrono::milliseconds>(crt_pt - last_pt) .count(); debug_stream << diff << " ms elapsed from" << " [ " << last_ln << " : " << last_func << " ]"; if(last_ln == built_ln) debug_stream << " (when built)"; debug_stream << " to" << " [ " << crt_ln << " : " << crt_func << " ]" << "\n"; last_pt = built_pt, last_ln = built_ln, last_func = built_func; } else { debug_stream << "[ " << crt_ln << " : " << crt_func << " ] " << "myclock_t::get failed (yet to be built!)\n"; } } }; #ifdef LOCAL myclock_t __myclock; #define build_clock() __myclock.build(__LINE__, __func__) #define set_clock() __myclock.set(__LINE__, __func__) #define get_clock() __myclock.get(__LINE__, __func__) #else #define build_clock() ((void)0) #define set_clock() ((void)0) #define get_clock() ((void)0) #endif namespace std { template <class RAitr> void rsort(RAitr __first, RAitr __last) { sort(__first, __last, greater<>()); } template <class T> size_t hash_combine(size_t seed, T const &key) { return seed ^ (hash<T>()(key) + 0x9e3779b9 + (seed << 6) + (seed >> 2)); } template <class T, class U> struct hash<pair<T, U>> { size_t operator()(pair<T, U> const &pr) const { return hash_combine(hash_combine(0, pr.first), pr.second); } }; template <class tuple_t, size_t index = tuple_size<tuple_t>::value - 1> struct tuple_hash_calc { static size_t apply(size_t seed, tuple_t const &t) { return hash_combine( tuple_hash_calc<tuple_t, index - 1>::apply(seed, t), get<index>(t)); } }; template <class tuple_t> struct tuple_hash_calc<tuple_t, 0> { static size_t apply(size_t seed, tuple_t const &t) { return hash_combine(seed, get<0>(t)); } }; template <class... T> struct hash<tuple<T...>> { size_t operator()(tuple<T...> const &t) const { return tuple_hash_calc<tuple<T...>>::apply(0, t); } }; template <class T, class U> istream &operator>>(std::istream &s, pair<T, U> &p) { return s >> p.first >> p.second; } template <class T, class U> ostream &operator<<(std::ostream &s, const pair<T, U> p) { return s << p.first << " " << p.second; } template <class T> istream &operator>>(istream &s, vector<T> &v) { for(T &e : v) { s >> e; } return s; } template <class T> ostream &operator<<(ostream &s, const vector<T> &v) { bool is_front = true; for(const T &e : v) { if(not is_front) { s << ' '; } else { is_front = false; } s << e; } return s; } template <class tuple_t, size_t index> struct tupleos { static ostream &apply(ostream &s, const tuple_t &t) { tupleos<tuple_t, index - 1>::apply(s, t); return s << " " << get<index>(t); } }; template <class tuple_t> struct tupleos<tuple_t, 0> { static ostream &apply(ostream &s, const tuple_t &t) { return s << get<0>(t); } }; template <class... T> ostream &operator<<(ostream &s, const tuple<T...> &t) { return tupleos<tuple<T...>, tuple_size<tuple<T...>>::value - 1>::apply( s, t); } template <> ostream &operator<<(ostream &s, const tuple<> &t) { return s; } string revstr(string str) { reverse(str.begin(), str.end()); return str; } } // namespace std #ifdef LOCAL #define dump(...) \ debug_stream << "[ " << __LINE__ << " : " << __FUNCTION__ << " ]\n", \ dump_func(#__VA_ARGS__, __VA_ARGS__) template <class T> void dump_func(const char *ptr, const T &x) { debug_stream << '\t'; for(char c = *ptr; c != '\0'; c = *++ptr) { if(c != ' ') debug_stream << c; } debug_stream << " : " << x << '\n'; } template <class T, class... rest_t> void dump_func(const char *ptr, const T &x, rest_t... rest) { debug_stream << '\t'; for(char c = *ptr; c != ','; c = *++ptr) { if(c != ' ') debug_stream << c; } debug_stream << " : " << x << ",\n"; dump_func(++ptr, rest...); } #else #define dump(...) ((void)0) #endif template <class P> void read_range(P __first, P __second) { for(P i = __first; i != __second; ++i) std::cin >> *i; } template <class P> void write_range(P __first, P __second) { for(P i = __first; i != __second; std::cout << (++i == __second ? '\n' : ' ')) { std::cout << *i; } } // substitute y for x. template <class T> void subst(T &x, const T &y) { x = y; } // substitue y for x iff x > y. template <class T> bool chmin(T &x, const T &y) { return x > y ? x = y, true : false; } // substitue y for x iff x < y. template <class T> bool chmax(T &x, const T &y) { return x < y ? x = y, true : false; } template <class T> constexpr T minf(const T &x, const T &y) { return std::min(x, y); } template <class T> constexpr T maxf(const T &x, const T &y) { return std::max(x, y); } // binary search. template <class int_t, class F> int_t bin(int_t ok, int_t ng, const F &f) { while(std::abs(ok - ng) > 1) { int_t mid = (ok + ng) / 2; (f(mid) ? ok : ng) = mid; } return ok; } // be careful that val is type-sensitive. template <class T, class A, size_t N> void init(A (&array)[N], const T &val) { std::fill((T *)array, (T *)(array + N), val); } void reset() { } template <class A, class... rest_t> void reset(A &array, rest_t... rest) { memset(array, 0, sizeof(array)); reset(rest...); } // a integer uniformly and randomly chosen from the interval [l, r). template <typename int_t> int_t rand_int(int_t l, int_t r) { static std::random_device seed_gen; static std::mt19937 engine(seed_gen()); std::uniform_int_distribution<int_t> unid(l, r - 1); return unid(engine); } // a real number uniformly and randomly chosen from the interval [l, r). template <typename real_t> real_t rand_real(real_t l, real_t r) { static std::random_device seed_gen; static std::mt19937 engine(seed_gen()); std::uniform_real_distribution<real_t> unid(l, r); return unid(engine); } /* The main code follows. */ #ifndef modint_hpp #define modint_hpp #include <cassert> #include <iostream> template <int mod> class modint { int val; public: constexpr long long value() const noexcept { return val; } constexpr modint() noexcept : val{0} {} constexpr modint(long long x) noexcept : val((x %= mod) < 0 ? mod + x : x) {} constexpr modint operator++(int) noexcept { modint t = *this; return ++val, t; } constexpr modint operator--(int) noexcept { modint t = *this; return --val, t; } constexpr modint &operator++() noexcept { return ++val, *this; } constexpr modint &operator--() noexcept { return --val, *this; } constexpr modint operator-() const noexcept { return modint(-val); } constexpr modint &operator+=(const modint &other) noexcept { return (val += other.val) < mod ? 0 : val -= mod, *this; } constexpr modint &operator-=(const modint &other) noexcept { return (val += mod - other.val) < mod ? 0 : val -= mod, *this; } constexpr modint &operator*=(const modint &other) noexcept { return val = (long long)val * other.val % mod, *this; } constexpr modint &operator/=(const modint &other) noexcept { return *this *= inverse(other); } constexpr modint operator+(const modint &other) const noexcept { return modint(*this) += other; } constexpr modint operator-(const modint &other) const noexcept { return modint(*this) -= other; } constexpr modint operator*(const modint &other) const noexcept { return modint(*this) *= other; } constexpr modint operator/(const modint &other) const noexcept { return modint(*this) /= other; } constexpr bool operator==(const modint &other) const noexcept { return val == other.val; } constexpr bool operator!=(const modint &other) const noexcept { return val != other.val; } constexpr bool operator!() const noexcept { return !val; } friend constexpr modint operator+(long long x, modint y) noexcept { return modint(x) + y; } friend constexpr modint operator-(long long x, modint y) noexcept { return modint(x) - y; } friend constexpr modint operator*(long long x, modint y) noexcept { return modint(x) * y; } friend constexpr modint operator/(long long x, modint y) noexcept { return modint(x) / y; } static constexpr modint inverse(const modint &other) noexcept { assert(other != 0); int a{mod}, b{other.val}, u{}, v{1}, t{}; while(b) t = a / b, a ^= b ^= (a -= t * b) ^= b, u ^= v ^= (u -= t * v) ^= v; return {u}; } static constexpr modint pow(modint other, long long e) noexcept { if(e < 0) e = e % (mod - 1) + mod - 1; modint res{1}; while(e) { if(e & 1) res *= other; other *= other, e >>= 1; } return res; } friend std::ostream &operator<<(std::ostream &os, const modint &other) noexcept { return os << other.val; } friend std::istream &operator>>(std::istream &is, modint &other) noexcept { long long val; other = {(is >> val, val)}; return is; } }; // class modint #endif // modint_hpp #ifndef binomial_hpp #define binomial_hpp namespace binomial { constexpr int mod = //* 998244353 /*/ 1000000007 /**/; constexpr int size = 1 << 19; using mint = modint<mod>; namespace { namespace internal_helper { struct fact_impl { int _fact[size], _inv[size], _invfact[size]; fact_impl() : _fact{1}, _inv{0, 1}, _invfact{1} { for(int i = 1; i < size; ++i) _fact[i] = (long long)_fact[i - 1] * i % mod; for(int i = 2; i < size; ++i) _inv[i] = mod - (long long)mod / i * _inv[mod % i] % mod; for(int i = 1; i < size; ++i) _invfact[i] = (long long)_invfact[i - 1] * _inv[i] % mod; } } fact_calced; } // namespace internal_helper mint fact(int x) noexcept { assert(x < size); return x < 0 ? 0 : internal_helper::fact_calced._fact[x]; } mint invfact(int x) noexcept { assert(x < size); return x < 0 ? 0 : internal_helper::fact_calced._invfact[x]; } mint inv(int x) noexcept { assert(x < size); return x < 0 ? 0 : internal_helper::fact_calced._inv[x]; } } // unnamed namespace mint binom(int n, int k) noexcept { return fact(n) * invfact(k) * invfact(n - k); } mint fallfact(int n, int k) noexcept { return fact(n) * invfact(n - k); } mint risefact(int n, int k) noexcept { return fallfact(n + k - 1, k); } // time complexity: O(min(n, k) * log(n)) mint stirling_2nd(int n, int k) noexcept { if(n < k) return 0; mint res{}; for(int i{}, j{k}; j >= 0; ++i, --j) if(i & 1) res -= mint::pow(j, n) * invfact(j) * invfact(i); else res += mint::pow(j, n) * invfact(j) * invfact(i); return res; }; // time complexity: O(min(n, k) * log(n)) mint bell(int n, int k) noexcept { if(n < k) k = n; mint res{}, alt{}; for(int i{}, j{k}; j >= 0; ++i, --j) { if(i & 1) alt -= invfact(i); else alt += invfact(i); res += alt * mint::pow(j, n) * invfact(j); } return res; } namespace internal_helper {} // namespace internal_helper } // namespace binomial #endif // binomial_hpp using namespace std; signed main() { void __solve(); void __precalc(); unsigned int t = 1; // cin >> t; // __precalc(); #ifdef LOCAL t = 3; #endif while(t--) { __solve(); } } using namespace binomial; void __solve() { int a, b, c; cin >> a >> b >> c; const int n=a+b+c; mint ans=0; mint po=mint::pow(mint(2),c); for(int i = c; i <= n-2; ++i,po*=2) { ans+=(po-1)*binom(i-1,c-1)*binom(i-c,b-1); } std::cout << ans << "\n"; }