読者です 読者をやめる 読者になる 読者になる

SRM578 GooseInZooDivOne

マンハッタン距離がdist以下のやつをunionfindでくっつけてから偶奇を見るだけ。
偶数のやつは何個使っても良くて、奇数のやつは偶数個使わなければいけないけど、
偶数のやつをP個, 奇数のやつをQ個とすれば
Q >= 1の時 2 ^ (P + Q - 1) - 1, Q = 0の時 2 ^ P - 1が答えとなる
(奇数のやつをQ - 1個目まで使うかどうか決めれば最後のやつ使うかどうかは勝手に決まるから)

#include <vector>
#include <cstdio>
#include <string>
using namespace std;

typedef long long ll;

#define rep(i, n) for(int i = 0; i < (int)n; ++i)

#define MOD (1000000007LL)


int cnt[5010];
int gu, ki;
ll r[5020];

struct unionfind{
    int par[5010], rank[5010];

    unionfind(){
	rep(i, 5010){
	    par[i] = i;
	    rank[i] = 0;
	}
    }

    inline int find(int x){
	if(par[x] == x) return x;
	else return par[x] = find(par[x]);
    }

    inline 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] = x;
	    if(rank[x] == rank[y]) rank[x]++;
	}
    }

}uf;


class GooseInZooDivOne{
    public:
	int count(vector <string> f, int d){
	    int h = f.size(), w = f[0].size();

	    rep(i, h){
		rep(j, w){
		    if(f[i][j] == 'v'){
			rep(k, h){
			    rep(l, w){
				if((i == k && j == l) || f[k][l] == '.') continue;
				int de = abs(i - k) + abs(j - l);
				if(de <= d) uf.unite(i * 60 + j, k * 60 + l);
			    }
			}
		    }
		}
	    }
	    
	    rep(i, h) rep(j, w) if(f[i][j] == 'v') ++cnt[uf.find(i * 60 + j)];
	    rep(i, h) rep(j, w) if(cnt[i * 60 + j] > 0){
		if(cnt[i * 60 + j] & 1) ki++;
		else gu++;
	    }

	    if(gu == 0 && ki < 2) return 0;

	    r[0] = 1LL;
	    rep(i, 5010) r[i + 1] = r[i] * 2 % MOD;

	    if(ki) --ki;
	    return r[ki + gu] - 1;
	}
};