SRM498 Div1 Medium(450) FoxStones - kusano

位置を交換できる石は、全てのマークからの距離が等しい石だけなので、マークからの距離でグループ分けをする。例えばそれぞれのグループの石の個数が4,2,3,1,2だったとしたら、答えは4!2!3!1!2!。

#include <map>
#include <vector>
using namespace std;

class FoxStones{public:
int getCount( int N, int M, vector <int> sx, vector <int> sy )
{
    int n = (int)sx.size();

    map<vector<int>,int> s;
    for ( int x=1; x<=N; x++ )
    for ( int y=1; y<=M; y++ )
    {
        vector<int> t(n);
        for ( int i=0; i<n; i++ )
            t[i] = max(abs(x-sx[i]),abs(y-sy[i]));
        if ( s.count(t) == 0 )
            s[t] = 0;
        s[t]++;
    }

    long long ans = 1;
    for ( map<vector<int>,int>::iterator it=s.begin(); it!=s.end(); it++ )
        for ( int i=1; i<=it->second; i++ )
            ans = ans*i%1000000009;
    return (int)ans;
}};