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; } };