SRM498 450pt: FoxStones

問題概要=解法

全てのマスについて、ある特定のマスについて距離が等しくなるような部分は任意に置換できる。全ての場合の数を求める問題。

感想

自分が参加していたSRMのMediumの中では1番か2番目に簡単だった問題(もう一つは高校数学の確率の問題)。実際に解けた人の数も相当多かった様だ。

const int MOD = 1000000009;

class FoxStones {
public:
int getCount(int N, int M, vector <int> sx, vector <int> sy) {
    map<vector<int>, int> dict;
    int S = sx.size();
    for(int i=1; i<=N; i++){
        for(int j=1; j<=M; j++){
            vector<int> tmp;
            for(int k=0; k<S; k++){
                tmp.push_back(max(abs(i-sx[k]), abs(j-sy[k])));
            }
            dict[tmp]++;
        }
    }
    int64 ans = 1;
    EACH(dict,it){
        int k = it->second;
        for(int i=1; i<=k; i++){
            ans = (ans * i)%MOD;
        }
    }
    return (int)ans;
}