kmjp's blog

競技プログラミング参加記です

AtCoder ABC #266 : G - Yet Another RGB Sequence

これはすんなり。
https://atcoder.jp/contests/abc266/tasks/abc266_g

問題

整数R,G,B,Kが与えられる。
'R','G','B'がそれぞれR,G,B個からなる文字列Sのうち、"RG"の並びがちょうどK個あるものは何通りか。

解法

包除原理で解く。
f(n) := "RG"を確定でn個以上含む組み合わせ
とすると、 \displaystyle f(n) = \frac{(R+G+B-n)!}{(R-n)!(G-n)!n!B!}となる。

g(n) := "RG"をちょうどn個含む組み合わせ
とすると、これは包除原理で  \displaystyle g(n) = \sum_{i=n} (-1)^{i-n} f(i)\times C(i,n)なのでg(K)を答えればよい。

int R,G,B,K;
const ll mo=998244353;

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

ll comb(ll N_, ll C_) {
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}

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>>R>>G>>B>>K;
	ll ret=0;
	for(i=K;i<=min(R,G);i++) {
		ll pat=fact[R+G+B-i]*factr[B]%mo*factr[R-i]%mo*factr[G-i]%mo*factr[i]%mo;
		if((i-K)%2==0) {
			ret+=pat*comb(i,K)%mo;
		}
		else {
			ret+=mo-pat*comb(i,K)%mo;
		}
	}
	cout<<ret%mo<<endl;
}

まとめ

最近のABCのG問題としては簡単な方かも。