mayoko’s diary

プロコンとかいろいろ。

SRM 545 div1 med: Spacetsk

問題

TopCoder Statistics - Problem Statement

L*H のグリッド平面が与えられる。以下の条件を満たす K 個の点の組は何通り考えられるか。

  • K 個の点は同一直線上にある
  • 上記の直線は, y = 0 において x 座標が整数になる
解法

K=1 の場合は, 答えは明らかに (L+1)*(H+1) です。ほかの場合を考えます。

直線の方向の場合分けは, (x, y) のベクトルで特徴づけることができます(x, y は互いに素とすればダブることもない)。
x = 0 の場合は特殊なので先にやっておくと, この場合は ( (H+1) choose (K) ) * (L+1) で片づけることができます。

ほかの場合は, x 座標の値が x 増えるごとに x 座標について点の数を数えたとき候補数が 1 減ることを利用すれば良いです。

const int MOD = 1e9+7;
ll mod_pow(ll x, ll p, ll MOD) {
    ll a = 1;
    while (p) {
        if (p%2) a = a*x%MOD;
        x = x*x%MOD;
        p/=2;
    }
    return a;
}

// mod_inverse
ll mod_inverse(ll a, ll m) {
    return mod_pow(a, MOD-2, m);
}

ll fact[2222], rfact[2222];

ll nCr(int n, int r) {
	if (n < r || r < 0) return 0;
	ll ret = fact[n];
	(ret *= rfact[n-r]) %= MOD;
	(ret *= rfact[r]) %= MOD;
	return ret;
}

class Spacetsk {
public:
	int countsets(int L, int H, int K) {
		fact[0] = rfact[0] = 1;
		for (int i = 1; i < 2222; i++) {
			fact[i] = (fact[i-1]*i)%MOD;
			rfact[i] = mod_inverse(fact[i], MOD);
		}
		if (K==1) return (L+1)*(H+1);
		if (K > H+1) return 0;
		// x=0
		ll ret = (L+1)*nCr(H+1, K) % MOD;
		for (int y = 1; y <= H; y++) {
			if ((K-1)*y > H) continue;
			int ynum = H/y+1;
			for (int x = 1; x <= L; x++) {
				if ((K-1)*x > L) continue;
				if (__gcd(y, x) > 1) continue;
				for (int i = 0, cnt = 1; i <= L; i+=x, cnt++) {
					if (cnt >= ynum) {
						ret += 2*(L-i+1)*nCr(cnt, K)%MOD;
						ret %= MOD;
						break;
					}
					ret += 2*min(x, L-i+1)*nCr(cnt, K)%MOD;
					ret %= MOD;
				}
			}
		}
		return ret;
	}
};