AtCoder ARC #061 : F - 3人でカードゲーム / Card Game for Three

部分点位は取りたかった…。
http://arc061.contest.atcoder.jp/tasks/arc061_d

問題

A,B,Cの3人でカードゲームを行う。
カードはa,b,cの３種類からなる。
A,B,Cは初期状態でN,M,K枚のカードを持つ。

最初はAの手番で始める。
自分の手番が来た状態の時、カードが無ければその人の勝ちである。
そうでない場合、カードの一番上のものをめくり、a,b,cなら次の手番はそれぞれA,B,Cとなる。また、そのカードは捨てる。

カードの組み合わせ3^(N+M+K)通りのうち、Aが勝利するのは何通りか。

解法

３人のカードを別々に考える必要はなく、(N+M+K)枚のカードを１列に並べよう。
先頭からカードを順に見て、b,cの登場回数がM,K回未満の間にaがN回出ればよい。

iターン目でAが勝利してゲームが終了する場合、その組み合わせの積は以下のとおりである。

• iターン目以降は何が出てもよいので3^(N+M+K-i)通り
• (i-1)ターン中(N-1)回aが出るのは通り
• (i-1)ターン中(i-N)回bかcが出る。かつb,cはM,K回以上でない場合は、たとえばcがk回出るとして通り

１つ目・２つ目の式はO(N)で解けるので問題ない。
３つ目の式は愚直に行うとO(NK)かかり、部分点にとどまる。

満点を取るためには、３つ目のcombinationのkに対する総和を求めなければならない。
例えば、L ≦ k ≦ Rとし、を求める事を考えよう。
なのは簡単にわかるので、とをそこから引けばよい。
１つ目の式を考えると、である。
はiが1つ小さいときに求めているはずなので、それを流用するとこの式はO(1)で求められる。
も同様に求めていけば良い。

int N,M,K;
ll mo=1000000007;
ll combi(ll N_, ll C_) {
	const int NUM_=1000001;
	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 modpow(ll a, ll n = mo-2) {
	ll r=1;
	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>>K;
	
	ll ret=0;
	ll C=1,L=0,R=0;
	for(int i=N;i<=N+M+K;i++) {
		ll a=combi(i-1,N-1)*modpow(3,N+M+K-i) % mo;
		if(i>N) C=C*2%mo;
		if(i==N+M+1) L=1;
		if(i>N+M+1) L=(L*2+combi(i-N-1,i-N-M-1))%mo;
		if(i==N+K+1) R=1;
		if(i>N+K+1) R=(R*2+combi(i-N-1,i-N-K-1))%mo;
		ret += a*(C-L-R+mo+mo) % mo;
	}
	
	
	cout<<ret%mo<<endl;
}

まとめ

１つに並べることが思いつかない時点でどうしようもない。