yukicoder : No.2391 SAN 値チェック 解説

久々にeが出てきたな。
https://yukicoder.me/problems/no/2391

問題

整数Xが与えられる。
Xが正である間、0以上1以下の整数値を1つ一様ランダムに選びXから引く。
この時の操作の期待値をAとすると、Aはsum(a_i * e^i)の形で表現できる。各a_iを求めよ。

解法

K回操作して和がX未満の場合、その確率×Kが解に計上される。
よって、Kを総当たりすることを考える。
K個の変数列Bを考えると、sum(B)＜Xかつ0≦B[i]≦1を満たすBのバリエーションだけ解に計上される。
このBのバリエーションは包除原理で表現出来、無限和を取る過程があるのでe^iが登場する。

ll N;
const ll mo=998244353;

const int NUM_=2000003;
static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];


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;
	
	inv[1]=fact[0]=factr[0]=1;
	for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
	for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	
	cin>>N;
	
	FOR(i,N+1) {
		cout<<modpow(mo-i,N-i)*factr[N-i]%mo<<endl;
	}
	
}

まとめ

eが出てくる問題はうまく無限和に落としこまないとな…。