#if defined(__GNUC__) && !defined(__clang__) #pragma GCC optimize("O3") #if defined(__x86_64__) || defined(__i386__) #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #endif #endif #include #include #define each(x, v) for (auto&& x : v) #define each2(x, y, v) for (auto&& [x, y] : v) #define rep(i,a,b) for(int i=(a);i<(b);i++) #define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--) #define all(x) begin(x),end(x) #define sz(x) (int)(x).size() using namespace std; using namespace atcoder; using ll=long long; using ull=unsigned long long; using ld=long double; using vll=vector; using vvll=vector; using vi=vector; using vvi=vector; using pll=pair; using pi=pair; // using mint=modint998244353; // using mint=modint1000000007; // using mint2=static_modint<2>; #line 2 "modint/montgomery-modint.hpp" template struct LazyMontgomeryModInt { using mint = LazyMontgomeryModInt; using i32 = int32_t; using u32 = uint32_t; using u64 = uint64_t; static constexpr u32 get_r() { u32 ret = mod; for (i32 i = 0; i < 4; ++i) ret *= 2 - mod * ret; return ret; } static constexpr u32 r = get_r(); static constexpr u32 n2 = -u64(mod) % mod; static_assert(mod < (1 << 30), "invalid, mod >= 2 ^ 30"); static_assert((mod & 1) == 1, "invalid, mod % 2 == 0"); static_assert(r * mod == 1, "this code has bugs."); u32 a; constexpr LazyMontgomeryModInt() : a(0) {} constexpr LazyMontgomeryModInt(const int64_t &b) : a(reduce(u64(b % mod + mod) * n2)){}; static constexpr u32 reduce(const u64 &b) { return (b + u64(u32(b) * u32(-r)) * mod) >> 32; } constexpr mint &operator+=(const mint &b) { if (i32(a += b.a - 2 * mod) < 0) a += 2 * mod; return *this; } constexpr mint &operator-=(const mint &b) { if (i32(a -= b.a) < 0) a += 2 * mod; return *this; } constexpr mint &operator*=(const mint &b) { a = reduce(u64(a) * b.a); return *this; } constexpr mint &operator/=(const mint &b) { *this *= b.inverse(); return *this; } constexpr mint operator+(const mint &b) const { return mint(*this) += b; } constexpr mint operator-(const mint &b) const { return mint(*this) -= b; } constexpr mint operator*(const mint &b) const { return mint(*this) *= b; } constexpr mint operator/(const mint &b) const { return mint(*this) /= b; } constexpr bool operator==(const mint &b) const { return (a >= mod ? a - mod : a) == (b.a >= mod ? b.a - mod : b.a); } constexpr bool operator!=(const mint &b) const { return (a >= mod ? a - mod : a) != (b.a >= mod ? b.a - mod : b.a); } constexpr mint operator-() const { return mint() - mint(*this); } constexpr mint operator+() const { return mint(*this); } constexpr mint pow(u64 n) const { mint ret(1), mul(*this); while (n > 0) { if (n & 1) ret *= mul; mul *= mul; n >>= 1; } return ret; } constexpr mint inverse() const { int x = get(), y = mod, u = 1, v = 0, t = 0, tmp = 0; while (y > 0) { t = x / y; x -= t * y, u -= t * v; tmp = x, x = y, y = tmp; tmp = u, u = v, v = tmp; } return mint{u}; } friend ostream &operator<<(ostream &os, const mint &b) { return os << b.get(); } friend istream &operator>>(istream &is, mint &b) { int64_t t; is >> t; b = LazyMontgomeryModInt(t); return (is); } constexpr u32 get() const { u32 ret = reduce(a); return ret >= mod ? ret - mod : ret; } static constexpr u32 get_mod() { return mod; } }; #line 2 "prime/factor-enumerate.hpp" vector factor_enumerate(int N) { vector lp(N + 1, 0); if (N < 2) return lp; vector pr{2, 3}; for (int i = 2; i <= N; i += 2) lp[i] = 2; for (int i = 3; i <= N; i += 6) lp[i] = 3; for (int i = 5, d = 4; i <= N; i += d = 6 - d) { if (lp[i] == 0) { lp[i] = i; pr.push_back(i); } for (int j = 2; j < (int)pr.size() && i * pr[j] <= N; ++j) { lp[i * pr[j]] = pr[j]; if (pr[j] == lp[i]) break; } } return lp; } using mint=LazyMontgomeryModInt<998244353>; using vm=vector; using vvm=vector; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); /** * O(X-C) * * 1. 条件の言い換え * * 各整数 x の初出時刻を T_x とする。 * 各 x は確率 1 でいつか出現することがわかる。 * * X>=1 のとき、ある時点で mex=X となる条件は * * T_X > max(T_0,...,T_{X-1}) * * すなわち、0,...,X の中で X が最後に初出することである。 * この確率を q とおけば、答えは 1-q。 * * X=0 なら答えは 1/(C+1)。 * 1<=X<=C なら、0,...,X は最初から対称なので答えは X/(X+1)。 * * 以下 C= 0} \binom{C+m}{C} z^m * * したがって t 回の遷移後は * * F_t(z) = (1-z)^{X+1} \sum_{m >= 0} \binom{C+m}{C} m^t z^m (1) * * これで F_t の係数全体は畳み込み 1 回で求まるが (つまり、元の問題をO(tlogt)で解ける)、 * 我々が必要なのは特定の重み付き和だけなので、以下はさらに高速化する。 * * 3. 重み付き和を 1 つの係数抽出に帰着 * * 各接頭辞の確率は共通で 1/A。ただし * * A = \prod_{i=1}^t (C+i) = \frac{X!}{C!}. * * よって * * q = \frac{S}{A} * * S = \sum_{d=0}^t \frac{f_{t,d}}{X+1-d} * * n=X+1, r=C+1 とおく。n=r+t。 * * 1/k が -log(1-z) の z^k の係数であることを利用する。 * deg F_t <= t より n-d >= r なので、次の級数で十分: * * L_r(z) = \sum_{k >= r}\frac{z^k}{k} * * 生成関数の積の係数は畳み込みなので * * S = [z^n]F_t(z)L_r(z) * * V(z) = (1-z)^nL_r(z) とおき、(1) を代入すると * * S = [z^n] (\sum_{m >= 0} \binom{C+m}{C} m^t z^m) V(z) * * L_r は z^r から始まり、(1-z)^n の定数項は 1 なので、 * V も z^r から始まる。そこで * * V(z) = \sum_{j >= 0} v_j z^{r+j} * * と定義する。 * * n=r+t だから、z^n の係数に寄与するのは m+j=t の項のみ。 * また t>0 なので m=0 の項は 0^t=0 により消える。 * したがって * * S = \sum_{m=1}^t \binom{C+m}{C} m^t v_{t-m} (2) * * * 4. v_j を再帰で計算 * * V の係数を畳み込みで求める必要はない。 * L_r は微分すると * * L_r'(z) = \sum_{k >= r} z^{k-1} = \frac{z^{r-1}}{1-z} * * となる(等比級数)。 * * V = (1-z)^n L_r を微分して整理すると、 * * (1-z)V'(z) + nV(z) = z^{r-1}(1-z)^n * * 両辺の z^{r+j-1} の係数を比較する。 * 左辺では V' から (r+j)v_j が、 * -zV'+nV から (n-r-j+1)v_{j-1} が現れる。 * n-r=t なので、v_{-1}=0 として * * (r+j)v_j + (t-j+1)v_{j-1} = (-1)^j\binom{n}{j} * * よって * * v_j = \frac{(-1)^j\binom{n}{j}-(t-j+1)v_{j-1}}{r+j} * * これにより必要な v_0,...,v_{t-1} を O(t) で計算できる! * * v_j を計算した後(2)を使えば全体的にO(t)で解ける(細かいところもあるが)。 * * 5. 細かいところ * * 頑張れば以下のように簡潔化できる * *  q = \sum_{j=0}^{t-1} \frac{(-1)^j(t-j)^t}{j!(t-j)!} w_j * w_0 = \frac{1}{C+1} * * 答えは 1-q。 * * w_j の漸化式と最終的な和はともに O(t)。 * 必要な k^t (1<=k<=t) も * * (ab)^t = a^t b^t * * と最小素因数の篩を使い、素数のみ累乗を計算することで * * O(t+pi(t)log t)=O(t) * * で列挙できる(pi(t)=O(t/log t) は素数の数)。 * * 逆数と逆階乗も一括逆元計算で O(t)。 * よって元の問題はO(t)で解ける */ int C,X; cin>>C>>X; if(X==0){ cout<=1;--j){ inv[j]*=prod; prod*=C+j; } ifac[t]=prod; for(int j=t;j>=1;--j)ifac[j-1]=ifac[j]*j; mint w=inv[1],q=pw[t]*ifac[t]*w; rep(j,1,t){ w=(mint(X+1)+mint(j*(t-j+1))*w)*inv[t+1-j]*inv[j+1]; if(j&1)q-=pw[t-j]*ifac[j]*ifac[t-j]*w; else q+=pw[t-j]*ifac[j]*ifac[t-j]*w; } cout<