SRM578

250

あるgooseから、マンハッタン距離がdist以下の鳥は必ずgooseになるので、距離がdist以下の鳥は全て同じ種類になります。

UnionFindを使うとどのように別れるかが分かります。それぞれのグループで鳥の個数が偶数のものと奇数のもので分けて数えて、偶数のグループで有れば、gooseでもそうではなくても良く、奇数のグループで有れば、最後の1組以外はgooseであってもなくても良いです。(最後の1組はそれ以外の組の種類によって一意に定まる)

組の数の合計をkとすると、
奇数の組があるときは、(2^(k-1) - 1) 通り
ないときは、(2^k - 1) 通り
になります。

#define MAX_N 5000
const int MOD =1000000007; 

struct UF {
	int par[MAX_N],rank[MAX_N];
	
	void init(int n){
		for(int i = 0; i < n; i++){
			par[i] = i;
			rank[i] = 0;
		}
	}
	
	int find(int x){
		if(par[x] == x){
			return x;
		}else{
			return par[x] = find(par[x]);
		}
	}
	
	void unite(int x, int y){
		x = find(x);
		y = find(y);
		if(x == y) return;
		
		if(rank[x] < rank[y]){
			par[x] = y;
		}else{
			par[y] = par[x];
			if(rank[x] == rank[y]) rank[y]++;
		}
	}
	
	bool same(int x, int y){
		return find(x) == find(y);
	}
};

int h,w,n;
int gs[3000];

int dist(int a, int b){
	int a1 = a/w, a2 = a%w;
	int b1 = b/w, b2 = b%w;
	return abs(a1-b1)+abs(a2-b2);
}



class GooseInZooDivOne {
public:
   int count( vector <string> g, int d ) {
	memset(gs,0,sizeof(gs));
	UF uf;
	vector<int> v;

	h = g.size();w = g[0].size();
	for(int i = 0; i < h; i++){
		for(int j = 0; j < w; j++){
			if(g[i][j] == 'v') v.push_back(i*w+j);
		}
	}

	n = v.size();
	uf.init(n);
	for(int i = 0; i < n; i++){
		for(int j = i+1; j < n; j++){
			if(dist(v[i],v[j])<=d)uf.unite(i,j);
		}
	}
	
	for(int i = 0; i < n; i++){
		gs[uf.find(i)]++;
	}

	int ev,od;
	ev = od = 0;
	for(int i = 0; i < n; i++){
		if(gs[i]){
			if(gs[i]%2)od++;
			else ev++;
		}
	}

	ll ans = 1LL;
	od--;
	if(od<0)od = 0;
	for(int i = 0; i < ev+od; i++){
		ans *= 2;
		ans %= MOD;
	}

	return ans-1;
   }
};

o-- 75pts
1412 -> 1428