結果
| 問題 | No.2105 Avoid MeX |
| コンテスト | |
| ユーザー |
C
|
| 提出日時 | 2026-11-19 15:22:36 |
| 言語 | C++23(gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 1 ms / 2,000 ms |
| + 969µs | |
| コード長 | 9,984 bytes |
| 記録 | |
| コンパイル時間 | 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 |
ソースコード
#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';
}
C