SRM 545 Div2 Hard SpacetskE

問題

http://apps.topcoder.com/stat?c=problem_statement&pm=12030&rd=14737
xy座標のX軸上を原点から座標(L,0)までの整数座標上において、ロケット任意の方向に１つだけ発射される。放たれたロケットはその方向に直線で進行し、0 <= x <= L, 0 <= y <= Hの間の格子点上でシグナルを発することができる（１つの格子点上で高々１回）。シグナルを進行中にK回発するとき、このような格子点の集合の数はいくつか。

やりかた

XY座標におけるエラトステネスの篩のような問題。
ロケットが放たれる座標(i, 0)ごとにロケットが通りうる座標をすべて見ていく方法を取る。まずロケットが通りうる座標というのはロケットが発射される座標をのぞけば0 <= x <= L, 1 <= y <= Hの間にある整数座標である。
y座標が小さい方から座標を列挙していこう。(i, 0)から放たれたロケットが座標(x, y)を通過する場合、このロケットは(i + (x - i) * n, (y * n)) = (i + Δx * n, Δy * n)の座標も通過しうることになる。この座標が0 〜 L, 0 〜 Hの間にあるならばこの点でもシグナルを発することができる。こうして(i, 0)から(x, y)に向けて放たれたロケットが許容された領域内で合計N回シグナルを発射できるとするならばこの場合のシグナル発の格子点の選び方は通りである。この後は通過する格子点(i + Δx * n, Δy * n)方向に発射するケースについては調べる必要はないので、調査済みのフラグを立てていけばいい。こうすることで(i, 0)からロケットが発射される場合については調べることができる。
あとは発射地点0~Lについて同じように調べて足しあわせればいい。
なお、K == 1の時は特殊で、許容領域内の格子点数が答えになる。

以下ソース。

const ll MOD = 1000000007;
const int MAX_COMB = 300;
ll comb[MAX_COMB + 1][MAX_COMB + 1];
bool visited[MAX_COMB + 1][MAX_COMB + 1];

class SpacetskE {
public:
  void combination(){
    comb[0][0] = 1;
    for(int i = 1; i < MAX_COMB + 1; i++){
      comb[i][0] = 1;
      for(int j = 1; j < MAX_COMB + 1; j++){
	comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % MOD;
      }
    }
  }
  int countsets(int L, int H, int K) {
    ll result = 0;
    if(K == 1) return (H + 1) * (L + 1);//K = 1の際は特殊ケース
    memset(comb, 0, sizeof(comb));
    combination();
    
    for(int i = 0; i <= L; i++){//すべての発射地点について調べる
      memset(visited, false, sizeof(visited));
      for(int y = 1; y <= H; y++){
	for(int x = 0; x <= L; x++){
	  if(visited[y][x]) continue;
	  int dy = y;
	  int dx = x - i;
	  int cnt = 0;

	  while(0 <= i + dx * cnt && i + dx * cnt <= L && 
		dy * cnt <= H){
	    visited[dy * cnt][i + dx * cnt] = true;
	    cnt++;
	  }
	  result = (result + comb[cnt][K]) % MOD;
	}
      }
    }
    return result;
  }
};

0 <= x <= H, 1 <= y <= Lとするミスをしていたためなかなかサンプルが通らなかったが、修正したらあっさり通った。やった！