mayoko’s diary

プロコンとかいろいろ。

SRM 498 div1 med:FoxStones

解法

色付きセルからの距離が等しい石同士は好きに入れ替えて良いので, そのような石が n 個あったとすると, それらの石の並べ方は n! 通りあります。これを掛け算するだけです。

const ll MOD = 1e9+9;

class FoxStones {
public:
    int getCount(int N, int M, vector <int> sx, vector <int> sy) {
        map<vector<int>, int> mm;
        int n = sx.size();
        for (int i = 0; i < n; i++) {
            sx[i]--; sy[i]--;
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                vector<int> v(n);
                for (int k = 0; k < n; k++) {
                    v[k] = max(abs(sx[k]-i), abs(sy[k]-j));
                }
                mm[v]++;
            }
        }
        ll ret = 1;
        for (auto p : mm) {
            int x = p.second;
            while (x) {
                (ret *= x--) %= MOD;
            }
        }
        return (int)ret;
    }
};