結果

問題 No.2105 Avoid MeX
コンテスト
ユーザー sortreew
提出日時 2022-10-21 23:33:27
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 541 ms / 2,000 ms
コード長 5,071 bytes
コンパイル時間 1,583 ms
コンパイル使用メモリ 171,672 KB
実行使用メモリ 16,584 KB
最終ジャッジ日時 2024-07-01 07:43:41
合計ジャッジ時間 6,121 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
#define YES "YES"
#define NO "NO"
#define Yes "Yes"
#define No "No"
#define DEFAULT              \
    LL ans = solve();        \
    if (ans == NONE)         \
    {                        \
    }                        \
    else                     \
    {                        \
        cout << ans << endl; \
    }
#define YESNO three(solve(), (OUT(YES), 1), (OUT(NO), 0))
#define YesNo three(solve(), OUT(Yes), OUT(No))
#define ECHO OUT(solve())
#define three(A, B, C) ((A) ? (B) : (C))
#define FOR(i, a, b) for (LL i = (a); i < (LL)(b); i++)
#define EFOR(i, a, b) for (LL i = (a); i <= (LL)(b); i++)
#define RFOR(i, a, b) for (LL i = (b - 1); i >= (LL)(a); i--)
#define REP(i, b) FOR(i, zero, b)
#define rep REP
#define EREP(i, b) EFOR(i, zero, b)
#define RREP(i, b) RFOR(i, zero, b)
#define ALL(c) c.begin(), c.end()
#define UNIQUE(c) \
    sort(ALL(c)); \
    c.erase(unique(ALL(c)), c.end())
#define MAX(c) (*max_element(ALL(c)))
#define MIN(c) (*min_element(ALL(c)))
#define MP make_pair
#define FI first
#define SE second
#define SI(x) (LL(x.size()))
#define PB push_back
#define DEBUG(a) OUT(a)
#define DEBUG2(a, b) OUT2(a, b)
#define cat cout << __LINE__ << endl
#define OUT(a) cout << (a) << endl
#define OUT2(a, b) cout << (a) << " " << (b) << endl
#define zero 0LL
#define all ALL
#define pb emplace_back
#define eb pb
#define int long long
using namespace std;
template <typename T>
inline void maximize(T &a, T b) { a = max(a, b); }
template <typename T>
inline void minimize(T &a, T b) { a = min(a, b); }
template <typename T>
inline bool middle(T a, T b, T c) { return b <= a && a <= c; }
template <class T>
inline bool MX(T &l, const T &r) { return l < r ? l = r, 1 : 0; }
template <class T>
inline bool MN(T &l, const T &r) { return l > r ? l = r, 1 : 0; }
typedef int LL;
typedef double ld;
typedef int ut;
typedef vector<ut> VI;
typedef vector<VI> VII;
typedef pair<ut, ut> pr;
typedef pair<ut, pr> ppr;
typedef vector<pr> Vpr;
typedef vector<ppr> Vppr;
typedef tuple<int, int, int, int> tapu;
typedef vector<tapu> Vtapu;
typedef priority_queue<pr, Vpr> PQ;
inline void outputVI(VI x)
{
    REP(i, SI(x)) { cout << three(i, " ", "") << x[i]; }
    OUT("");
}
const int SIZE1 = 5e5 + 1000;
const int SIZE2 = 5010;
const int SIZE3 = 430;
const int SIZE = SIZE1;
const int MAPSIZE = 40;
const LL p998 = 998244353;
const LL p107 = 1000000007;
const LL p = p107;
const LL INF = 1LL << 60;
const long double EPS = 1e-7;
const LL NONE = -2;
#define endl "\n"
ut N, M, D, Q, I, S, V, F;
VI edges[SIZE];
LL vals[SIZE], answer = zero;
// LL A[SIZE],B[SIZE],C[SIZE];
LL C, X, Y, K, P;
#include <cstdint>

template <std::uint_fast64_t Modulus>
class modint
{
    using u64 = std::uint_fast64_t;

public:
    u64 a;

    constexpr modint(const u64 x = 0) noexcept : a(x % Modulus) {}
    constexpr u64 &value() noexcept { return a; }
    constexpr const u64 &value() const noexcept { return a; }
    constexpr modint operator+(const modint rhs) const noexcept
    {
        return modint(*this) += rhs;
    }
    constexpr modint operator-(const modint rhs) const noexcept
    {
        return modint(*this) -= rhs;
    }
    constexpr modint operator*(const modint rhs) const noexcept
    {
        return modint(*this) *= rhs;
    }
    constexpr modint operator/(const modint rhs) const noexcept
    {
        return modint(*this) /= rhs;
    }
    constexpr modint &operator+=(const modint rhs) noexcept
    {
        a += rhs.a;
        if (a >= Modulus)
        {
            a -= Modulus;
        }
        return *this;
    }
    constexpr modint &operator-=(const modint rhs) noexcept
    {
        if (a < rhs.a)
        {
            a += Modulus;
        }
        a -= rhs.a;
        return *this;
    }
    constexpr modint &operator*=(const modint rhs) noexcept
    {
        a = a * rhs.a % Modulus;
        return *this;
    }
    constexpr modint &operator/=(modint rhs) noexcept
    {
        u64 exp = Modulus - 2;
        while (exp)
        {
            if (exp % 2)
            {
                *this *= rhs;
            }
            rhs *= rhs;
            exp /= 2;
        }
        return *this;
    }
};
LL solve()
{
    cin >> C >> X;
    vector<modint<p998>> dp(2200), n_dp(2200);
    if (X == 0)
    {
        return (modint<p998>(1) / (C + 1)).a;
    }
    dp[0] = 1;
    REP(i, C + X + 2)
    {
        LL target = C + i + 1;
        if (target >= X + 1)
            break;
        REP(j, target + 1)
        {
            n_dp[j] += dp[j] * j;
            n_dp[j + 1] += dp[j] * (target - j);
        }
        REP(j, X + 1)
        {
            dp[j] = n_dp[j] / target;
            n_dp[j] = 0;
        }
    }
    modint<p998> ans = 1;

    REP(i, X + 1)
    {
        modint<p998> nokori = dp[i];
        ans -= dp[i] / (X - i + 1);
    }

    return ans.a;
    return (modint<p998>(1) - modint<p998>(1) * 2000 / 2001).a;
}
signed main()
{

    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    LL T = 1;
    REP(i, T)
    {
        DEFAULT;
    }
    return 0;
}
0