kojingharangの日記

SRM 578 Div1 250 GooseInZooDivOne （追記あり）

12:19 |

• W*H grid の各セルに鳥がいるかいないかが与えられる。
• ガチョウは２羽以上の偶数羽いて、ガチョウからマンハッタン距離 D 以内の鳥はガチョウである。
• 可能なガチョウの配置の組み合わせ数を mod 1,000,000,007 で求める問題。
• 1≦W, H≦50
• 1≦D≦100

• あるセルがガチョウだとした場合にガチョウと確定する鳥たちを同値類としてその構成人数を数えていく
• Even = 偶数羽のグループ個数, Odd = 奇数羽のグループ個数として
• Even は独立に採用/不採用できて, Odd は偶数個だけ一度に採用できるので
• ( 2^Even * ΣCombination(Odd, i) (for i in Odd 以内の偶数) ) - 1 (0個の分) が答え。

• 1,000,000,007 は素数なので逆元のやつを使用

• 最後のサンプルが 40 分ほどずっと合わなくておわり

• （あとで）

• Each bird within Manhattan distance dist of any goose is also a goose.
• ぴったりじゃなくて "within" でした＼(^o^)／

• Accepted in practice room

#define MAXN 10010
ll facts[MAXN];
ll inv_facts[MAXN];

static const ll MODVAL = 1000000007;
ll MODADD(ll x, ll y) { return (x+y)%MODVAL; }
ll MODSUB(ll x, ll y) { return (x-y+MODVAL)%MODVAL; }
ll MODMUL(ll x, ll y) { return (x*y)%MODVAL; }
ll MODPOW(ll x, ll e) { ll v = 1; for(;e;x=MODMUL(x,x),e>>=1) if(e&1) v = MODMUL(v, x); return v; }
ll MODINV(ll x) { return MODPOW(x, MODVAL-2); }
ll MODCOMB(ll n, ll r) {
	assert(0<=n && n<MAXN);
	assert(0<=r && r<=n);
	ll vv = MODMUL(facts[n], MODMUL(inv_facts[r], inv_facts[n-r]));
	return vv;
}

void gen_facts() {
	facts[0] = 1;
	inv_facts[0] = MODINV(facts[0]);
	RANGE(i, 1, MAXN) facts[i] = MODMUL(facts[i-1], i);
	RANGE(i, 1, MAXN) inv_facts[i] = MODMUL(inv_facts[i-1], MODINV(i));
	
	REP(i, MAXN) assert(MODMUL(facts[i], inv_facts[i])==1);
}

int co=0;
int W, H;
void f(vector<string>& F, int D, int x, int y) {
	if(F[y][x]!='v') return;
	co++;
	F[y][x]='x';
	
	REP(yy, H) REP(xx, W) {
		if(abs(yy-y)+abs(xx-x) <= D) {
			if(0<=xx && xx<W && 0<=yy && yy<H && F[yy][xx]=='v') {
				f(F, D, xx, yy);
			}
		}
	}
}

class GooseInZooDivOne {
	public:
	int count(vector <string> F, int D) {
		gen_facts();
		H=F.size();
		W=F[0].size();
		int even=0, odd=0;
		int sum=0;
		int sumCo=0;
		REP(y, H) REP(x, W) if(F[y][x]=='v') sum++;
		REP(y, H) {
			REP(x, W) {
				if(F[y][x]=='v') {
					co=0;
					f(F, D, x, y);
					if(co&1) odd++; else even++;
					//cout<<"co "<<co<<endl;
					//cout<<F<<endl;
					sumCo+=co;
				}
			}
		}
		assert(sum==sumCo);
		cout<<even<<" "<<odd<<endl;
		ll ea = 1;
		REP(i, even) {
			ea = (ea * 2) % MODVAL;
		}
		ll oa = 0;
		for(int i=0;i<=odd;i+=2) {
			oa = (oa + MODCOMB(odd, i)) % MODVAL;
		}
		cout<<ea<<" "<<oa<<endl;
		return (((ea * oa) % MODVAL) - 1 + MODVAL) % MODVAL;
	}
};

• （追記）

• ΣnCi (iは偶数) == 2^(n-1) を使うとちょっと簡潔になりました
• (accepted in practice room)

static const ll MODVAL = 1000000007;

int co;
int W, H;
void f(vector<string>& F, int D, int x, int y) {
	if(F[y][x]!='v') return;
	F[y][x]='x';
	co++;
	
	REP(yy, H) REP(xx, W) {
		if(abs(yy-y)+abs(xx-x) <= D) {
			if(0<=xx && xx<W && 0<=yy && yy<H && F[yy][xx]=='v') {
				f(F, D, xx, yy);
			}
		}
	}
}

class GooseInZooDivOne {
	public:
	int count(vector <string> F, int D) {
		H=F.size();
		W=F[0].size();
		int even=0, odd=0;
		REP(y, H) REP(x, W) {
			if(F[y][x]=='v') {
				co=0;
				f(F, D, x, y);
				if(co&1) odd++; else even++;
			}
		}
		ll ans = 1;
		REP(i, even + max(0, odd-1)) ans = (ans * 2) % MODVAL;
		return (ans - 1 + MODVAL) % MODVAL;
	}
};

ツイートする