Submission #31453926
Source Code Expand
// #define NDEBUG #include <bits/stdc++.h> namespace kod { using i8 = std::int8_t; using i16 = std::int16_t; using i32 = std::int32_t; using i64 = std::int64_t; using i128 = __int128_t; using u8 = std::uint8_t; using u16 = std::uint16_t; using u32 = std::uint32_t; using u64 = std::uint64_t; using u128 = __uint128_t; using f64 = double; using f80 = long double; } // namespace kod /** * @brief 数値型のエイリアス */ namespace kod { namespace util { template <class F> struct FixedPoint : private F { explicit constexpr FixedPoint(F&& f) : F(std::forward<F>(f)) {} template <class... Args> constexpr decltype(auto) operator()(Args&&... args) const { return F::operator()(*this, std::forward<Args>(args)...); } }; template <class F> constexpr FixedPoint<F> fixed(F&& f) { return FixedPoint<F>(std::forward<F>(f)); } } // namespace util } // namespace kod /** * @brief 不動点コンビネータ */ namespace kod { namespace util { class ForwardRange { int src, dst; public: explicit constexpr ForwardRange(const int l, const int r) : src(l), dst(r) {} explicit constexpr ForwardRange(const int n) : src(0), dst(n) {} constexpr ForwardRange begin() const { return *this; } constexpr std::monostate end() const { return {}; } constexpr bool operator!=(std::monostate) const { return src < dst; } constexpr void operator++() const {} constexpr int operator*() { return src++; } }; class BackwardRange { int src, dst; public: explicit constexpr BackwardRange(const int l, const int r) : src(r), dst(l) {} explicit constexpr BackwardRange(const int n) : src(n), dst(0) {} constexpr BackwardRange begin() const { return *this; } constexpr std::monostate end() const { return {}; } constexpr bool operator!=(std::monostate) const { return src > dst; } constexpr void operator++() const {} constexpr int operator*() { return --src; } }; using rep = ForwardRange; using revrep = BackwardRange; } // namespace util } // namespace kod /** * @brief 昇順・降順走査 */ namespace kod { namespace util { template <class T> constexpr bool setmin(T& x, const T& y) { if (x > y) { x = y; return true; } return false; } template <class T> constexpr bool setmax(T& x, const T& y) { if (x < y) { x = y; return true; } return false; } } // namespace util } // namespace kod /** * @brief 比較代入 */ namespace kod { namespace util { template <class T> void print(T&& x) { std::cout << x; } template <class T, class... Args> void print(T&& x, Args&&... args) { std::cout << x << ' '; print(std::forward<Args>(args)...); } void println() { std::cout << '\n'; } template <class... Args> void println(Args&&... args) { print(std::forward<Args>(args)...); std::cout << '\n'; } template <class C> void print_seq(C&& c, const char* sep = " ", const char* end = "\n") { bool f = false; for (auto&& x : std::forward<C>(c)) { if (f) { std::cout << sep; } else { f = true; } std::cout << x; } std::cout << end; } } // namespace util } // namespace kod /** * @brief 標準出力ユーティリティ */ namespace kod { namespace util { template <class T> T scan() { T x; std::cin >> x; return x; } template <class T> std::vector<T> scan_vec(int n = -1) { if (n == -1) std::cin >> n; assert(n >= 0); std::vector<T> v(n); for (auto& x : v) std::cin >> x; return v; } template <class T, int N> std::array<T, N> scan_array() { std::array<T, N> a; for (auto& x : a) std::cin >> x; return a; } std::vector<char> scan_chars() { std::string s; std::cin >> s; return std::vector<char>(std::cbegin(s), std::cend(s)); } } // namespace util } // namespace kod /** * @brief 標準入力ユーティリティ */ #include <atcoder/convolution> #include <atcoder/modint> namespace ext { template <class M> struct FpUtil { static M fact(const int n) { static std::vector<M> vec; assert(n >= 0); if (vec.empty()) vec = {M(1)}; for (int i = vec.size(); i <= n; ++i) vec.push_back(vec.back() * M(i)); return vec[n]; } static M inv(const int n) { static std::vector<M> vec; assert(n > 0); if (vec.empty()) vec = {M(0), M(1)}; for (int i = vec.size(); i <= n; ++i) vec.push_back(-M(M::mod() / i) * vec[M::mod() % i]); return vec[n]; } static M inv_fact(const int n) { static std::vector<M> vec; assert(n >= 0); if (vec.empty()) vec = {M(1)}; for (int i = vec.size(); i <= n; ++i) vec.push_back(vec.back() * inv(i)); return vec[n]; } static M binom(const int n, const int k) { assert(0 <= k and k <= n); return fact(n) * inv_fact(n - k) * inv_fact(k); } static M factpow(const int n, const int k) { assert(0 <= k and k <= n); return fact(n) * inv_fact(n - k); } static M homo(const int n, const int k) { assert((n == 0 and k == 0) or (n > 0 and k >= 0)); if (n == 0 and k == 0) return M(1); return binom(n + k - 1, k); } }; } // namespace ext namespace solution { using namespace kod; using namespace util; using std::array; using std::pair; using std::tuple; using std::vector; constexpr i32 inf32 = std::numeric_limits<i32>::max() / 2; constexpr i64 inf64 = std::numeric_limits<i64>::max() / 2; using Fp = atcoder::modint998244353; using Util = ext::FpUtil<Fp>; Fp inv_binom(const int n, const int k) { return Util::inv_fact(n) * Util::fact(n - k) * Util::fact(k); } void main() { const int n = scan<int>(); const int m = scan<int>(); // Fp ans = 0; // for (const int i : rep(n + 1)) { // for (const int j : rep(m + 1)) { // ans += Fp(std::max(i, j)) * Util::binom(n, i) * Util::binom(m, j) / Util::binom(n // + m, i + j) / (i + j); // } // } vector<Fp> f1(n + 1), f2(n + 1), g1(m + 1), g2(m + 1); for (const int i : rep(n + 1)) { f1[i] = Util::binom(n, i); f2[i] = f1[i] * i; } for (const int j : rep(m + 1)) { g1[j] = Util::binom(m, j); g2[j] = g1[j] * j; } vector<Fp> h(n + m + 1); fixed([&](auto&& dfs, const int l, const int r) -> void { if (l > n or l > m) { return; } if (r - l <= 60) { for (const int i : rep(l, std::min(n + 1, r))) { for (const int j : rep(l, std::min(m + 1, r))) { if (i < j) { h[i + j] += f1[i] * g2[j]; } if (j < i) { h[i + j] += f2[i] * g1[j]; } } } return; } const int mid = (l + r) / 2; dfs(l, mid); dfs(mid, r); if (mid <= m) { vector<Fp> f(f1.begin() + l, f1.begin() + std::min(n + 1, mid)); vector<Fp> g(g2.begin() + mid, g2.begin() + std::min(m + 1, r)); auto tmp = atcoder::convolution(std::move(f), std::move(g)); for (const int k : rep(tmp.size())) { h[k + l + mid] += tmp[k]; } } if (mid <= n) { vector<Fp> f(f2.begin() + mid, f2.begin() + std::min(n + 1, r)); vector<Fp> g(g1.begin() + l, g1.begin() + std::min(m + 1, mid)); auto tmp = atcoder::convolution(std::move(f), std::move(g)); for (const int k : rep(tmp.size())) { h[k + l + mid] += tmp[k]; } } })(0, n + m + 1); Fp ans = 0; for (const int k : rep(1, std::min(n, m) + 1)) { ans += Util::binom(n, k) * Util::binom(m, k) * inv_binom(n + m, k + k) * Util::inv(k + k) * k; } for (const int k : rep(1, n + m + 1)) { ans += h[k] * inv_binom(n + m, k) * Util::inv(k); } println(ans.val()); } } // namespace solution int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout << std::fixed << std::setprecision(20); int cases = 1; // std::cin >> cases; while (cases--) solution::main(); return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Yes or No |
User | KoD |
Language | C++ (GCC 9.2.1) |
Score | 2000 |
Code Size | 8460 Byte |
Status | AC |
Exec Time | 751 ms |
Memory | 32648 KiB |
Judge Result
Set Name | Sample | Partial | All | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1500 / 1500 | 500 / 500 | ||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt |
Partial | sample_01.txt, sample_02.txt, sample_04.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt |
All | sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_2_01.txt, subtask_2_02.txt, subtask_2_03.txt, subtask_2_04.txt, subtask_2_05.txt, subtask_2_06.txt, subtask_2_07.txt, subtask_2_08.txt, subtask_2_09.txt, subtask_2_10.txt, subtask_2_11.txt, subtask_2_12.txt, subtask_2_13.txt, subtask_2_14.txt, subtask_2_15.txt, subtask_2_16.txt, subtask_2_17.txt, subtask_2_18.txt, subtask_2_19.txt, subtask_2_20.txt, subtask_2_21.txt, subtask_2_22.txt, subtask_2_23.txt, subtask_2_24.txt, subtask_2_25.txt, subtask_2_26.txt, subtask_2_27.txt, subtask_2_28.txt, subtask_2_29.txt, subtask_2_30.txt, subtask_2_31.txt, subtask_2_32.txt, subtask_2_33.txt, subtask_2_34.txt, subtask_2_35.txt, subtask_2_36.txt, subtask_2_37.txt, subtask_2_38.txt, subtask_2_39.txt, subtask_2_40.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 10 ms | 3576 KiB |
sample_02.txt | AC | 3 ms | 3652 KiB |
sample_03.txt | AC | 3 ms | 3600 KiB |
sample_04.txt | AC | 4 ms | 3588 KiB |
sample_05.txt | AC | 4 ms | 3512 KiB |
subtask_1_01.txt | AC | 2 ms | 3516 KiB |
subtask_1_02.txt | AC | 2 ms | 3604 KiB |
subtask_1_03.txt | AC | 2 ms | 3520 KiB |
subtask_1_04.txt | AC | 2 ms | 3580 KiB |
subtask_1_05.txt | AC | 2 ms | 3516 KiB |
subtask_1_06.txt | AC | 2 ms | 3520 KiB |
subtask_1_07.txt | AC | 2 ms | 3572 KiB |
subtask_1_08.txt | AC | 2 ms | 3520 KiB |
subtask_1_09.txt | AC | 3 ms | 3672 KiB |
subtask_1_10.txt | AC | 2 ms | 3612 KiB |
subtask_1_11.txt | AC | 4 ms | 3720 KiB |
subtask_1_12.txt | AC | 8 ms | 3704 KiB |
subtask_1_13.txt | AC | 23 ms | 4032 KiB |
subtask_1_14.txt | AC | 42 ms | 5048 KiB |
subtask_1_15.txt | AC | 148 ms | 8680 KiB |
subtask_1_16.txt | AC | 147 ms | 8804 KiB |
subtask_1_17.txt | AC | 147 ms | 8820 KiB |
subtask_1_18.txt | AC | 148 ms | 8804 KiB |
subtask_1_19.txt | AC | 147 ms | 8792 KiB |
subtask_1_20.txt | AC | 147 ms | 8800 KiB |
subtask_1_21.txt | AC | 147 ms | 8804 KiB |
subtask_1_22.txt | AC | 146 ms | 8820 KiB |
subtask_1_23.txt | AC | 147 ms | 8448 KiB |
subtask_1_24.txt | AC | 144 ms | 8072 KiB |
subtask_1_25.txt | AC | 141 ms | 8068 KiB |
subtask_2_01.txt | AC | 3 ms | 3512 KiB |
subtask_2_02.txt | AC | 3 ms | 3520 KiB |
subtask_2_03.txt | AC | 3 ms | 3516 KiB |
subtask_2_04.txt | AC | 709 ms | 30552 KiB |
subtask_2_05.txt | AC | 700 ms | 30568 KiB |
subtask_2_06.txt | AC | 702 ms | 30620 KiB |
subtask_2_07.txt | AC | 701 ms | 30496 KiB |
subtask_2_08.txt | AC | 701 ms | 30608 KiB |
subtask_2_09.txt | AC | 704 ms | 30688 KiB |
subtask_2_10.txt | AC | 704 ms | 30640 KiB |
subtask_2_11.txt | AC | 705 ms | 30620 KiB |
subtask_2_12.txt | AC | 706 ms | 30660 KiB |
subtask_2_13.txt | AC | 701 ms | 30692 KiB |
subtask_2_14.txt | AC | 701 ms | 30612 KiB |
subtask_2_15.txt | AC | 704 ms | 30552 KiB |
subtask_2_16.txt | AC | 733 ms | 32648 KiB |
subtask_2_17.txt | AC | 751 ms | 30356 KiB |
subtask_2_18.txt | AC | 712 ms | 27212 KiB |
subtask_2_19.txt | AC | 672 ms | 24068 KiB |
subtask_2_20.txt | AC | 47 ms | 16612 KiB |
subtask_2_21.txt | AC | 48 ms | 16860 KiB |
subtask_2_22.txt | AC | 55 ms | 16756 KiB |
subtask_2_23.txt | AC | 62 ms | 16816 KiB |
subtask_2_24.txt | AC | 72 ms | 18064 KiB |
subtask_2_25.txt | AC | 71 ms | 18924 KiB |
subtask_2_26.txt | AC | 73 ms | 18868 KiB |
subtask_2_27.txt | AC | 74 ms | 17912 KiB |
subtask_2_28.txt | AC | 90 ms | 18972 KiB |
subtask_2_29.txt | AC | 101 ms | 19120 KiB |
subtask_2_30.txt | AC | 263 ms | 22396 KiB |
subtask_2_31.txt | AC | 428 ms | 24236 KiB |
subtask_2_32.txt | AC | 704 ms | 30680 KiB |
subtask_2_33.txt | AC | 728 ms | 30684 KiB |
subtask_2_34.txt | AC | 725 ms | 30844 KiB |
subtask_2_35.txt | AC | 740 ms | 28560 KiB |
subtask_2_36.txt | AC | 742 ms | 28588 KiB |
subtask_2_37.txt | AC | 313 ms | 17656 KiB |
subtask_2_38.txt | AC | 139 ms | 15560 KiB |
subtask_2_39.txt | AC | 722 ms | 28260 KiB |
subtask_2_40.txt | AC | 245 ms | 22124 KiB |