yukicoder : No.2105 Avoid MeX

こっちはコードが短いね。
https://yukicoder.me/problems/no/2105

問題

整数C,Xが与えられる。

1-originであるN要素の整数列Aを、A[i]が0～(C+i-1)のうちいずれかの正整数を1つ等確率で選んだものとする。
AのprefixのMexがいずれもXとならない確率をP(N)とする。Nを無限大にしたときのP(N)の極限値を求めよ。

解法

X=0の場合は、A[1]=0なら条件を満たすので、1/(C+1)である。
以下Xが正のケースを考える。
Nが大きくなると、各値xがA中に現れない確率は0になっていく。
そこで、「AのprefixのMexがいずれもXとならない」という条件は、Aのprefix内でX以下の値がすべて1回以上登場したとき、初回の登場が一番遅いのがX以外であることに等しい。

C+i＞Xとなるiでは、0～Xの登場確率はいずれも1/(1+X)で等しい。
C+i≦Xとなるiでは、C+i未満の値が確率1/(C+i)で現れる。
これを踏まえ、C+iがX以下であるiにおいて、X未満の値が何個出てくるか、それぞれに対する確率をDPで求めよう。

int C,X;
const ll mo=998244353;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

ll from[4020];
ll to[4020];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>C>>X;
	if(X==0) {
		cout<<modpow(C+1)<<endl;
		return;
	}
	
	from[0]=1;
	for(i=1;C+i<=X;i++) {
		ZERO(to);
		FOR(j,X) {
			//new
			(to[j+1]+=from[j]*(C+i-j)%mo*modpow(C+i)%mo)%=mo;
			(to[j]+=from[j]*j%mo*modpow(C+i)%mo)%=mo;
		}
		swap(from,to);
	}
	ll ret=0;
	FOR(i,X+1) ret+=from[i]*(X-i)%mo*modpow(X+1-i)%mo;
	cout<<ret%mo<<endl;
}

まとめ

コードは短いけど、考察は★3.5でもいい気がする。