TopCoder SRM 545 Div2 Hard SpacetskE、Div1 Medium Spacetsk

この回はMediumの方がめんどくさい…。
http://community.topcoder.com/stat?c=problem_statement&pm=11937
http://community.topcoder.com/stat?c=problem_statement&pm=12030

問題

宇宙船を打ち上げるspaceportの長さはLである。
また、信号を送れる高度をHとする。

宇宙船を打ち上げるとき、以下の条件を満たして打ち上げたい。

• X軸上(0,0)-(L,0)のどこかの格子点から打ち上げる。
• 宇宙船は打ち上げ後直進する。なお、打ち上げの向きはY軸成分が正でなければならない。
• 宇宙船が(0,0)-(L,H)の領域を通過するとき、格子点でのみ信号を送ることができる。
• 信号はぴったりK回送らなければいけない。

宇宙船の信号の送り方の組み合わせ数を答えよ。

なお、Div1とDiv2の違いはL,H,Kの上限であり、Div1の方がDiv2の10倍である。

解法

K==1の時は全格子点について、そこを通過する打ち上げ方が可能なので答えは格子点の数である(L+1)*(H+1)。
以降はK>1の時について。

まずは左方向の打ち上げは置いておき上と右上だけ考える。

• 上方向に打ち上げる場合、高さ0～(H+1)個のうちK個の点を選択するので選び方は通り。
• 右上方向に打ち上げる場合、打ち上げ位置を原点として(X,Y)の位置でK個目の信号を送り終えると仮定する。その場合、(X,Y)がK個目で、それまでの格子点で(K-1)個の信号を送るので、X,Yの最大公約数をGとして通り。

後は各発射位置に対し、各格子点(X,Y)をK個目とする組み合わせを累積していけばよい。
以下のコードでは、Y座標分を事前に累積した値(pr)を使っている。

ll mo=1000000007;
ll comb(int P_,int Q_) {
	static const int N_=1020;
	static ll C_[N_][N_];
	
	if(C_[0][0]==0) {
		int i,j;
		FOR(i,N_) C_[i][0]=C_[i][i]=1;
		for(i=1;i<N_;i++) for(j=1;j<i;j++) C_[i][j]=(C_[i-1][j-1]+C_[i-1][j])%mo;
	}
	if(P_<0 || P_>N_ || Q_<0 || Q_>P_) return 0;
	return C_[P_][Q_];
}
ll pr[201];

class SpacetskE {
	public:
	int countsets(int L, int H, int K) {
		int i,x,x2,y;
		ll ret=0;
		
		if(K==1) return (L+1)*(H+1);
		
		ZERO(pr);
		for(x=0;x<=L;x++) {
			for(y=1;y<=H;y++) {
				int g=__gcd(x,y);
				if(g+1>=K) pr[x] = (pr[x] + comb(g,K-1)) % mo;
			}
		}
		FOR(x,L+1) FOR(x2,L+1) ret += pr[abs(x-x2)];
		return ret%mo;
		
	}
};

まとめ

これはすんなり解法が思い浮かんだ。
Div2 Hardの時のO(LH)の解法でDiv1も通るね。
同じ直線でも信号を送る位置が違うなら別組み合わせ、というのが若干ややこしいね。