Codeforces ECR #163 : F. Rare Coins

言い換えに気付けば簡単。
https://codeforces.com/contest/1948/problem/F

問題

N個の鞄があり、i番には金貨A[i]枚、銀貨B[i]枚が入っている。
金貨の価値は常に1で、銀貨はそれぞれ1/2の確率で0または1の価値となる。

クエリとして区間[L,R]が与えられる。
区間[L,R]に含まれる鞄内の金貨・銀貨の価値の総和が、その他の鞄内の金貨・銀貨の価値の総和を超える確率を求めよ。

解法

累積和を計算すれば、区間内外の金貨・銀貨の枚数はわかる。
区間内外の銀貨のうち価値1の枚数を総当たりするとクエリ毎にO(sum(B))かかり間に合わない。

ただ、これは言い方を変えると「区間内の銀貨のうち価値1のものと、区間外の銀貨のうち価値0のものの枚数が合計何枚以上ならよい」といえる。
結局、sum(B)毎の銀貨のうち一定枚数以上が狙ったものが出る確率と考えておくと、前処理で累積和の要領で値を計算しておけば、クエリ毎にO(1)で回答できる。

int N,Q;
ll SA[303030];
ll SB[303030];
const ll mo=998244353;

ll comb(ll N_, ll C_) {
	const int NUM_=2400001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		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;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}

ll CS[5404040];


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>>Q;
	FOR(i,N) {
		cin>>x;
		SA[i+1]=SA[i]+x;
	}
	FOR(i,N) {
		cin>>x;
		SB[i+1]=SB[i]+x;
	}
	
	ll r2=modpow(modpow(2,SB[N]));
	for(i=SB[N];i>=0;i--) {
		CS[i]=(comb(SB[N],i)+CS[i+1])%mo;
	}
	
	while(Q--) {
		int L,R;
		cin>>L>>R;
		ll g0=SA[R]-SA[L-1];
		ll s0=SB[R]-SB[L-1];
		ll g1=SA[N]-g0;
		ll s1=SB[N]-s0;
		
		
		if(g0>g1+s1) {
			cout<<1<<" ";
		}
		else {
			cout<<CS[g1+s1-g0+1]*r2%mo<<" ";
		}
	}
	cout<<endl;
	
	
}

まとめ

この類の組み合わせ問題、ちょくちょく忘れるんだよな。