SRM498 Div1 Medium

450

マークのある地点までの距離をが等しい箇所を数えてしまって良い。
同じ地点が F 箇所ある場合、ただの並び替えなので F 階乗パターン。

int dist(pair<int, int> a, pair<int, int> b)
{
  return max(abs(a.first - b.first), abs(a.second - b.second));
}

class FoxStones {
public:
  int getCount(int N, int M, vector <int> sj, vector <int> si)
  {
    swap(N, M);
    map< vector<int>, int > cnt;
    vector< pair<int, int> > marked;
    for (int k = 0; k < si.size(); ++k) {
      marked.push_back(make_pair(si[k] - 1, sj[k] - 1));
    }
    sort(marked.begin(), marked.end());

    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < M; ++j) {
        if (binary_search(marked.begin(), marked.end(), make_pair(i, j))) continue;
        vector<int> u;
        for (int k = 0; k < marked.size(); ++k) {
          u.push_back(dist(make_pair(i, j), marked[k]));
        }
        ++cnt[u];
      }
    }

    const lli mod = 1000000009;
    const int F = 200 * 200 + 10;
    lli fact[F];
    fact[0] = 1;
    for (lli i = 1; i < F; ++i) {
      fact[i] = fact[i - 1] * i;
      fact[i] %= mod;
    }
    lli ret = 1;
    each (i, cnt) {
      ret *= fact[i->second];
      ret %= mod;
    }
    return ret;
  }
}