kmjp's blog

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

天下一プログラマーコンテスト2014 決勝 : D - 高橋君

その他コンテスト

数学ゲーと思ったら違った。
本番は部分点のみ。
http://tenka1-2014-final-open.contest.atcoder.jp/tasks/tenka1_2014_final_d

問題

n,kからなるクエリが計Q個与えられる。
各クエリにおいて、0,1からなるn文字の文字列のうち、1の数がk個以下となるものの数を答えよ。

解法

{}_n S_k = \sum_{i=0}^k {}_n C_iとなる表記Sを定義すると、 {}_n S_kが答えとなる。
部分点の範囲では、 {}_n C_i及び {}_n S_iの全列挙がO(N^2)なので、事前に全列挙すればクエリ処理と合わせO(Q+N^2)で間に合う。

ただ、満点解法ではO(N^2)の処理は間に合わない。
ここで、 {}_n S_kの特性を考えると {}_n S_k = {}_n S_{k-1} + {}_n C_k = {}_n S_{k-1} + {}_{n-1} C_{k} + {}_{n-1} C_{k-1} = {}_{n-1} S_{k-1} + {}_{n-1} S_{k}とCombinationと同じような特性になる。
ただしCombinationと異なり、Sはk>nの時 {}_n S_k = {}_n S_nとなる点がことなる。

ここで、平方分割を用いる。例えば分割の間隔をpとすると、Sのうちnを一定ごと、たとえばpの倍数の部分だけ {}_n S_kを列挙しておく。
事前に階乗計算をしておくと {}_n C_kはO(1)で求められるので、Sの部分列挙はO(N^2/P)で済む。

求めるクエリn,kに対し、n=ap+bとなるa,b(b＜p)を考える。
\displaystyle {}_{ap+b} S_k = {}_{ap+b-1} S_{k-1} + {}_{ap+b-1} S_{k}
\displaystyle = {}_{ap+b-2} S_{k-2} + 2*{}_{ap+b-2} S_{k-1} + {}_{ap+b-2} S_{k} + 2*{}_{ap+b-2} S_{k}
\displaystyle = \sum_{i=0}^b {}_{ap} S_{k-i}*{}_b C_i
と変形できるので、事前計算したSを用いてO(b)＜O(p)で処理できる。

よって部分列挙O(N^2/p)、クエリ処理O(Qp)なので、p=√NとするとO((Q+N)√N)で済む。

int T,N,K;
ll mo=1000000007;
int S[201][100001];

ll combi(ll N_, ll C_) {
	const int NUM_=200001;
	static ll fact[NUM_+1],factr[NUM_+1];
	int i;
	if (fact[0]==0) {
		vector<ll> inv(NUM_ + 1);
		inv[1]=fact[0]=factr[0]=1;
		for (i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		
		FOR(i,NUM_) fact[i+1]=fact[i]*(i+1)%mo, factr[i+1]=factr[i]*inv[i+1]%mo;
	}
	if(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;
	
	for(y=0;y<=100000;y+=500) {
		FOR(x,100001) S[y/500][x]=((x?S[y/500][x-1]:0)+combi(y,x))%mo;
	}
	
	cin>>T;
	while(T--) {
		cin>>N>>K;
		ll ret=0;
		FOR(i,1+(N%500)) if(K-i>=0) ret+=S[N/500][K-i]*combi(N%500,i)%mo;
		cout<<ret%mo<<endl;
	}
}

まとめ

割とシンプルな回答だと思うけどどうだろ。