経路 [AtCoder Beginner Contest 034 C]

atcoder.jp

答えは

・(H+W-2)! / (H-1)! * (W-1)! % 1000000007

です。

部分点50点は上記の式を計算するだけ、部分点100点はDPをすることで得られますが、
満点101点は W,H<=10^5 と数字が非常に大きいので、計算やDPでは解くことができません。

満点を得るためにはフェルマーの小定理（？）、逆元（？）などを求める必要があるみたいなんですが、あいにくどちらもわかりません。そこで、前回作成した「階乗を高速に求めるメソッド」を使って、力業で解いてみることにしました。

jpliterature.hatenablog.com

式をあらかじめ約分する

H=6, W=4 のときを考えてみます。上記の式は、

%1000000007

となります。分子と分母とで被っている数があるので、これを約分してあらかじめ取り除いておきます。

%1000000007

ほかにも約分できる個所がありますが、今回はやらなくても間に合うみたいです。

ソースコード

void solve () {

	int w = nextInt(), h = nextInt();
	int big = Math.max(w, h) - 1;
	int small = Math.min(w, h) - 1;

	BigInteger divisor = bigFactorial(2, small-1);　//約分した後の残りの部分だけをかけ合わせる
	BigInteger dividend = bigFactorial(big+1, small);

	BigInteger ans = dividend.divide(divisor);
	ans = ans.mod(BigInteger.valueOf(1000000007));

	out.println(ans);

}


static BigInteger bigFactorial (int s, int leng) {
	BigInteger[] ar = new BigInteger[leng];
	for (int i=0; i<leng; i++) {
		ar[i] = BigInteger.valueOf(i+s);
	}
	int t = 1, length = ar.length;
	while (t <= length) {
		for (int i=0; i<length; i+=(t<<1)) {
			if (t+i < length) {
				ar[i] = ar[i].multiply(ar[i+t]);
				ar[i+t] = null;
			}
		}
		System.gc(); //null代入と合わせてMLEを乗り切る
		t = t<<1;
	}
	return ar[0];
}

このプログラムを提出したところ、実行時間1340ms/2000ms 、メモリ182MB/256MB となってギリギリ通すことができました。こんな回りくどいことやってないで数学を勉強しろよ、と言われそうですが、BigInteger と分割統治法のいい練習になったので、個人的には満足してます。