SRM545 Div1 Medium

500

ある点を最後にシグナルを発信する位置にする。
その点から原点までの間に整数座標の点がいくつあるかを、GCDで求める。
その中から K - 1 コの点を選ぶ組み合わせだけ、選び方が存在する。

原点のから以外にも同様な線分を引くことができるので、その分を掛け算する。

K == 1 の時だけ別処理。

const lli mod = 1000000007;

const int N = 2000 + 5;
lli nCk[N][N];

void f(void)
{
  for (int i = 0; i < N; ++i) {
    nCk[i][i] = nCk[i][0] = 1;
  }
  for (int i = 0; i < N; ++i) {
    for (int j = 1; j < i; ++j) {
      nCk[i][j] = nCk[i - 1][j - 1] + nCk[i - 1][j];
      nCk[i][j] %= mod;
    }
  }
  return ;
}

class Spacetsk {
public:
  int countsets(int L, int H, int K)
  {
    if (K == 1) {
      return (H + 1) * (L + 1);
    }

    f();

    lli sum = 0;
    sum += (L + 1) * nCk[H + 1][K];
    sum %= mod;

    for (int i = 1; i <= H; ++i) {
      for (int j = 1; j <= L; ++j) {
        int x = __gcd(max(i, j), min(i, j));
        sum += nCk[x][K - 1] * (L - j + 1) * 2;
        sum %= mod;
      }
    }

    return sum;
  }
};