TopCoder SRM 498 Medium FoxStones

問題

NxMマスのグリッドにそれぞれ異なる数が書かれている。
n個のマスには印がついていて、それらの座標はsx[i],sy[i]で与えられる。


それぞれのマスにかかれた数を入れ替えた配置のうち、
全ての印のついたマスからの距離が変わらない配置はいくつあるか、
mod 10^9+9で求めよ。


ただし、(a,b)と(c,d)の距離はmax{|a-c|,|b-d|}とする。

制約条件

N,M≦200
n≦50

方針

ナイーブに距離でマスを分類していけばよい。


具体的には、1つの印に対して、
全てのマスを距離によって分類する。
(今までのグループのID,今回距離によってついたID)を
座標圧縮すれば、0〜40000の整数になるので、
それを新しい「今までのグループのID」とする、


という操作を繰り返せばよい。
40000マスをn回座標圧縮する感じ。
制限時間がかなりギリギリの解法。

ソースコード

int h,w;
pi num[200][200];
void func(int y,int x){
	num[y][x]=mp(-1,-1);
	set<pi> p;
	rep(i,h)rep(j,w)if(num[i][j]!=mp(-1,-1)){
		
		num[i][j].second=max(abs(i-y),abs(j-x));
		p.insert(num[i][j]);
	}
	map<pi,int> M;
	int k=0;
	fr(i,p)M[*i]=k++;
	rep(i,h)rep(j,w)if(num[i][j]!=mp(-1,-1)){
		num[i][j].first=M[num[i][j]];
	}
}
const int mod=1000000009;
int cnt[40000], fact[40000];

class FoxStones {
	public:
	int getCount(int N, int M, vector <int> sx, vector <int> sy) 
	{
		h=N; w=M;
		int n=sx.size();
		memset(num,0,sizeof(num));
		memset(cnt,0,sizeof(cnt));
		rep(i,n)func(sx[i]-1,sy[i]-1);
		
		rep(i,h)rep(j,w)if(num[i][j]!=mp(-1,-1))cnt[num[i][j].first]++;
		fact[0]=1;
		rep(i,40000-1)fact[i+1]=fact[i]*(i+1ll)%mod;
		ll ans=1;
		rep(i,40000)ans=ans*fact[cnt[i]]%mod;
		return (int)ans;
	}
};