読者です 読者をやめる 読者になる 読者になる

TopCoder SRM 545 Div1 Medium: Spacetsk

競技プログラミング SRM

コード

public class Spacetsk {

    private final int MOD = (int) 1e9 + 7;

    public int countsets(int L, int H, int K) {
	if (K == 1) {
	    return ((L + 1) * (H + 1)) % MOD;
	}

	// パスカルの三角形
	int N = Math.max(Math.max(L + 2, H + 2), K + 2);
	int[][] nCm = new int[N][N];
	for (int i = 0; i < N; i++) {
	    nCm[i][0] = 1;
	    for (int j = 1; j <= i; j++) {
		nCm[i][j] = (nCm[i - 1][j - 1] + nCm[i - 1][j]) % MOD;
	    }
	}

	long ans = 0;
	for (int lastX = 1; lastX <= L; lastX++) {
	    for (int lastY = 1; lastY <= H; lastY++) {
		// (0, 0)から発射して(lastX, lastY) で最後に信号を発するとする
		int gcd = gcd(lastX, lastY);// (lastX, lastY)の前にある格子点の数
		int launch = (L + 1 - lastX);// 発射地点のパターン数

		// 左右に打ち上げるので2倍する
		ans += (long) nCm[gcd][K - 1] * launch * 2;
		ans %= MOD;
	    }
	}

	// 垂直に打ち上げる
	ans += (long) nCm[H + 1][K] * (L + 1);
	ans %= MOD;

	return (int) ans;
    }

    private int gcd(int a, int b) {
	if (b == 0) {
	    return a;
	}
	return gcd(b, a % b);
    }
}