kmjp's blog

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

AtCoder ARC #012 : D - Don't worry. Be Together

ARC

かなり苦戦したけどようやく解けた…。
http://arc012.contest.atcoder.jp/tasks/arc012_4

問題

N人の人間が２次元座標状上に存在し、時間1ごとに上下左右のいずれか1マス動く。
各人の座標が与えられたとき、時間T後に全員が原点に戻る場合の数を答えよ。
なお、数が大きくなる場合があるので、moduloで割った余りの数を答える。

解法

下記Σを外す処理がわからなかったので下記サイトを参考にしました。
External Memory ARC #012 D : Don't worry. Be Together
ARC12 D - Don’t worry. Be Together - math314の日記

まず各人が座標(x,y)にいるとすると、その人が原点に戻る場合の数を考える。
これをN人分掛け合わせればよい。

x,yがいずれも正であるとして、この人が時間T後に原点にいるには以下を満たさなければならない。

  • x+y <= T
  • T-(x+y)が偶数

前者はわかりやすく、x+y>Tだと原点に戻れないので明らか。
後者は、最短では時間(x+y)で原点に戻れるので残りの時間分T-(x+y)余裕があるが、これが奇数だと余分x,y方向に移動した分戻れないので、偶数でなければならない。

ここで、T-(x+y)=2mとする。
(x,y)から(0,0)に最短で向かう場合x回左、y回下に行くわけだが、この場合2m分余分に時間があるのでm回右または上に移動し、同じ回数余分に左または下に移動しても原点に戻れる。
よって、m回のうち右に移動する回数をi回とすると、上に移動する回数が(m-i)回なので全組み合わせは\sum_{i=0}^m \frac{T!}{(x+i)!i!(y+(m-i))!(m-i)!}となる。
ここで、このΣが邪魔なので外すことを考える。
{}_{x+m}C_{m-i}=\frac{(x+m)!}{(x+i)!(m-i)!}、{}_{y+m}C_{i}={}_{T-(x+m)}C_{i}=\frac{(y+m)!}{(y+(m-i))!i!}で、かつ{}_{T}C_{x+m}=\frac{T!}{(x+m)!(T-(x+m)!}=\frac{T!}{(x+m)!(y+m)!}であることを考えると、先のΣの式は{}_T C_{x+m}\sum_{i=0}^m ({}_{x+m}C_{m-i}\times{}_{T-(x+m)}C_{i}) と変形できる。

ここで、このΣの中を考えると、(x+m)個から(m-i)個選び、(T-(x+m))個からi個選ぶ、という処理を各iに対して行うということは、結局T個からm個選ぶということなるので、この式は
\sum_{i=0}^m \frac{T!}{(x+i)!i!(y+(m-i))!(m-i)!}={}_T C_{x+m}\times{}_T C_{m}=\frac{T!T!}{(x+m)!(T-(x+m))!m!(T-m)!}

ここで、これらの階乗処理を毎回行うのは重いので、後でまとめて行う。
N人それぞれに対して、各数の階乗が分子にくる回数を累積し、分母にくる数を減算する。
x!を掛け合わせる数をP_xとすると、 ( (1!)^{P_1}\times(2!)^{P_2}\times...\times(T!)^{P_T}) % moduloを求めればよい。

あいにく、P_xは負になることもあり、除算が発生することもある。
よって、まずimos法により、P_xを累積して各数を掛ける回数Q_xをもとめる。(Q_x=P_x+P_{x+1}+...+P_Tになる)
また、Xが合成数の場合、その数を約数に加算する。たとえばQ_6の分はQ_2とQ_3に加算する。

後は各素数yに対して、y^{Q_y}を掛け合わせればよい。

int N,T;
ll MO;
int nt;
int num[1000003];
int numt[1000003];

ll modpow(ll A,ll B,ll M) {
	// A^B mod M
	ll res=1;
	ll t=A;
	while(B) {
		if(B%2==1) res=(res*t) % M;
		t=(t*t) % M;
		B>>=1;
	}
	return res;
}

void solve() {
	int r,i,j,k,l;
	int x,y,mx,my;
	
	GET2(&N,&T);
	MO=GETi();
	
	FOR(i,N) {
		int x=abs(GETi());
		int y=abs(GETi());
		if(x+y>T || (T-(x+y))%2) {
			_P("0\n");
			return;
		}
		int m=(T-(x+y))/2;
		
		num[x+m]--;
		num[T-(x+m)]--;
		num[m]--;
		num[T-m]--;
		num[T]+=2;
	}
	
	numt[1000002]=num[1000002];
	for(i=1000001;i>=0;i--) numt[i]=numt[i+1]+num[i];
	
	for(i=1000001;i>=2;i--) {
		if(numt[i]==0) continue;
		for(k=2;k*k<=i;k++) {
			if(i%k==0) {
				numt[i/k]+=numt[i];
				numt[k]+=numt[i];
				numt[i]=0;
				break;
			}
		}
	}
	
	ll res=1;
	for(i=2;i<1000003;i++) if(numt[i]) res=(res*modpow(i,numt[i],MO))%MO;
	
	_P("%lld\n",res);
	
	return;
}

まとめ

他人のコードを読んでも、上記の式でΣを外せることがなかなかわからなかった。
Combinationの特性はもうちょい勉強した方がいいな。

合成数のmoduloに大して階乗とかCombinationの計算をするのは初めてだが、幸いそこはすんなり書けた。
この知見は今後も役に立ちそうだ。