結果

問題 No.2105 Avoid MeX
コンテスト
ユーザー C
提出日時 2026-11-19 15:22:36
言語 C++23(gcc16)
(gcc 16.2.0 + boost 1.92.0 + ACL)
コンパイル:
g++-16 -O2 -fplugin=/usr/lib/yukicoder/noavx512-gcc16.so -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 1 ms / 2,000 ms
+ 969µs
コード長 9,984 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 6,996 ms
コンパイル使用メモリ 421,848 KB
実行使用メモリ 9,868 KB
最終ジャッジ日時 2026-11-19 15:22:45
合計ジャッジ時間 9,237 ms
ジャッジサーバーID
(参考情報)
judge4_0 / judge3_0
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 6
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code

#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 <bits/stdc++.h>
#include <atcoder/all>
#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<ll>;
using vvll=vector<vll>;
using vi=vector<int>;
using vvi=vector<vi>;
using pll=pair<ll,ll>;
using pi=pair<int,int>;

// using mint=modint998244353;
// using mint=modint1000000007;
// using mint2=static_modint<2>;

#line 2 "modint/montgomery-modint.hpp"

template <uint32_t mod>
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<mod>(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<int> factor_enumerate(int N) {
  vector<int> lp(N + 1, 0);
  if (N < 2) return lp;
  vector<int> 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<mint>;
using vvm=vector<vm>;

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<X とし、t=X-C とおく。
	 * 最初の t 回は X が出現できず、それ以降は 0,...,X が対称になる。
	 * 最初の t 回に現れた異なる値の個数を D とすると、
	 * 未出現の X+1-D 個の値のうち、X が最後に現れる確率は 1/(X+1-D)。
	 * よって
	 * 
	 * q = \sum_{d=0}^t Pr[d] * \frac{1}{X+1-d}
	 * 
	 * 2. 生成関数を考える
	 *
	 * f_{i,d} = 長さ i で異なる値が d 個の接頭辞の個数
	 * 
	 *   F_i(z) = \sum_{d\ge 0} f_{i,d} z^d
	 * 
	 * とする。初期値は F_0(z)=1。
	 *
	 * 次の値は C+i+1 通りあり、既出値を選ぶ d 通りでは D は不変、
	 * 未出値を選ぶ C+i+1-d 通りでは D が 1 増える。
	 * zF_i' が各係数に d を掛けることを使うと
	 * 
	 *   F_{i+1}(z) = z(1-z)F_i'(z) + (C+i+1)zF_i(z)
	 * 
	 * ここで微分の積の法則に注目する。
	 * a=C+i+1 とおけば、
	 * 
	 *   (1-z)F_i' + aF_i = (1-z)^{a+1} (\frac{F_i}{(1-z)^a})'
	 * 
	 * そこで
	 * 
	 *   G_i(z) = \frac{F_i(z)}{(1-z)^{C+i+1}}
	 * 
	 * とすると
	 * 
	 *   G_{i+1}(z) = zG_i'(z)
	 * 
	 * となる。元の DP では係数が混ざるが、この変換後は
	 * z^m の係数が毎回 m 倍されるだけで、他の係数と混ざらない。
	 *
	 * 初期値は負の二項定理より
	 * 
	 *   G_0(z) = (1-z)^{-(C+1)} = \sum_{m >= 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<<mint(C+1).inverse()<<'\n';
		return 0;
	}
	if(X<=C){
		cout<<mint(X)/mint(X+1)<<'\n';
		return 0;
	}
	int t=X-C;
	auto lp=factor_enumerate(t);
	vm pw(t+1);
	pw[1]=1;
	for(int k=2;k<=t;++k){
		const int&p=lp[k];
		if(p==k)pw[k]=mint(k).pow(t);
		else pw[k]=pw[p]*pw[k/p];
	}
	vm inv(t+1),ifac(t+1);
	mint prod=1;
	for(int j=2;j<=t;++j)prod*=j;
	for(int j=1;j<=t;++j){
		inv[j]=prod;
		prod*=C+j;
	}
	prod=prod.inverse();
	for(int j=t;j>=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<<mint(1)-q<<'\n';
}
0