AtCoder ABC #154 : F - Many Many Paths

まぁこれは見たことあったしなぁ。
https://atcoder.jp/contests/abc154/tasks/abc154_f

問題

(0,0)から右または上の隣接する格子点をたどって移動し、最後(r,c)に到達したとする。
到達位置がR1≦r≦R2、C1≦c≦C2であるような移動経路は何通りか。

解法

パスカルの三角形上の長方形区間の総和を求める問題になる。
f(n,c) := Comb(n,0)+Comb(n,1)+...+Comb(n,c)
とする。これは三角形のn行目における先頭(c+1)要素の総和となる。

各ラインごとに加減算して、求める長方形区間に含まれる部分の総和を求めていこう。
次のラインに移動するとき、以下を知っておくと直前の結果からの変化量を高速に求めることができる。
f(n+1,c) = f(n,c)*2-Comb(n,c)
f(n+1,c+1) = f(n,c)*2+Comb(n,c)

const ll mo=1000000007;
ll comb(ll N_, ll C_) {
	const int NUM_=2400001;
	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;
}

int X1,Y1,X2,Y2;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>X1>>Y1>>X2>>Y2;
	ll ret=0;
	ll pat=0;
	FOR(i,Y1+1) pat+=comb(X1+Y1,i);
	ret=pat;
	for(y=Y1+1;y<=Y2;y++) {
		pat=(pat*2+comb(X1+y-1,y))%mo;
		(ret+=pat)%=mo;
	}
	for(x=X1+1;x<=X2;x++) {
		pat=(pat*2+mo-comb(x+Y2-1,x-1))%mo;
		(ret+=pat)%=mo;
	}
	pat=0;
	FOR(i,Y1) pat+=comb(X1+Y1,i);
	ret-=pat;
	for(x=X1+2;x<=X2+1;x++) {
		pat=(pat*2+mo-comb(x+Y1-2,x-1))%mo;
		ret-=pat;
	}
	for(y=Y1;y<Y2;y++) {
		pat=(pat*2+comb(X2+1+y-1,X2))%mo;
		ret-=pat;
	}
	
	cout<<(ret%mo+mo)%mo<<endl;
	
}

まとめ

でも今回はAC1000名以下だったのね。