yukicoder : No.895 MESE

参加が遅れて全完できず。
https://yukicoder.me/problems/no/895

問題

整数a,b,cが与えられる。
整数X,Y,Zの組で、以下を満たすものについてZの総和を求めよ。

• X＞Y＞Z
• X,Y,Zの2進数表記はa,b,c個1が立っている
• X or Y or Zは2^(a+b+c)-1

解法

(a+b+c)桁の2進数において、Yの最上位ビットを総当たりしよう。
例えば下から(0-originで)y桁目に最上位ビットが来るとする。

ここで、z桁目が1となるのがZである場合の組み合わせを考える。
y桁より上はXに属するのが確定するので、下y桁のうち、z桁目を除いた(y-1)桁のうち、(c-1)桁はZ、(b-1)桁はYに属す。
よってその組み合わせはComb(y-1,c-1)*Comb(y-c,b-1)通りである。
実際にはその数だけ2^zが加算される。zが0～(y-1)の各位置を取ることを考えると、yに対しComb(y-1,c-1)*Comb(y-c,b-1)*(2^y-1)の総和を取ればよい。

int A,B,C;
ll mo=1000000007;
ll p2[303030];
ll comb(ll N_, ll C_) {
	const int NUM_=400001;
	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;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A>>B>>C;
	int D=A+B+C;
	p2[0]=1;
	FOR(i,301010) p2[i+1]=p2[i]*2%mo;
	
	ll ret=0;
	for(i=1;i<D-1;i++) {
		ll c=comb(i-1,C-1)*comb(i-C,B-1)%mo*(p2[i]-1)%mo;
		ret+=c;
	}
	cout<<ret%mo<<endl;
}

まとめ

微妙に一ズレで手間取った。