SRM498 Div1 Medium

450

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

view plainprint?

1. int dist(pair<int, int> a, pair<int, int> b)  
2. {  
3.   return max(abs(a.first - b.first), abs(a.second - b.second));  
4. }  
5.   
6. class FoxStones {  
7. public:  
8.   int getCount(int N, int M, vector <int> sj, vector <int> si)  
9.   {  
10.     swap(N, M);  
11.     map< vector<int>, int > cnt;  
12.     vector< pair<int, int> > marked;  
13.     for (int k = 0; k < si.size(); ++k) {  
14.       marked.push_back(make_pair(si[k] - 1, sj[k] - 1));  
15.     }  
16.     sort(marked.begin(), marked.end());  
17.   
18.     for (int i = 0; i < N; ++i) {  
19.       for (int j = 0; j < M; ++j) {  
20.         if (binary_search(marked.begin(), marked.end(), make_pair(i, j))) continue;  
21.         vector<int> u;  
22.         for (int k = 0; k < marked.size(); ++k) {  
23.           u.push_back(dist(make_pair(i, j), marked[k]));  
24.         }  
25.         ++cnt[u];  
26.       }  
27.     }  
28.   
29.     const lli mod = 1000000009;  
30.     const int F = 200 * 200 + 10;  
31.     lli fact[F];  
32.     fact[0] = 1;  
33.     for (lli i = 1; i < F; ++i) {  
34.       fact[i] = fact[i - 1] * i;  
35.       fact[i] %= mod;  
36.     }  
37.     lli ret = 1;  
38.     each (i, cnt) {  
39.       ret *= fact[i->second];  
40.       ret %= mod;  
41.     }  
42.     return ret;  
43.   }  
44. }  

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