yukicoder : No.1670 Many Gacha

これ系の問題、以前も見た気がするのに思い出せなかった…。
https://yukicoder.me/problems/no/1670

問題

1～N番のN種類のフィギュアをそろえたい。
M種類のガチャがあり、各ガチャiを引くと、1～A[i]番のフィギュアのいずれかが等確率で手に入る。
各種類フィギュアのそれぞれ最低1個以上そろえるのに必要なガチャを引く回数の最小値の期待値を求めよ。

解法

選ぶガチャとしては、未入手の最大番号のガチャを、最大確率で引くのが最適。

• F(x):= x番のガチャを最大確率で引けるガチャjにおけるA[j]の値(=x番のガチャを引くまでの回数の期待値)
• E(x):= 未入手のガチャ番号の最大値がxである回数の期待値
• P(x):= 未入手のガチャ番号の最大値がxである状態を経由する確率

とすると、解はsum(E(x))=sum(P(x)F(x))となる。
P(x)は、x番以降のガチャのうちx番を最後に入手する確率で、x番以降のガチャは等確率で手に入るのでP(x)=1/(N-x+1)。

int N,M;
int A[202020];
int B[202020];
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;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) cin>>A[i];
	ll ret=0;
	FOR(i,N) {
		B[i]=*lower_bound(A,A+M,i+1);
		ret+=B[i]*modpow(N-i)%mo;
	}
	cout<<ret%mo<<endl;
	
	
}

まとめ

うーん、何を数え上げるかが難しい。