Codeforces #184 Div2. D. Olya and Graph

またちょっと変わったグラフ問題。
http://codeforces.com/contest/305/problem/D

問題

1～NのN個の点からなる有向グラフと、数Kが与えられる。
このグラフが以下を満たすようにしたい。

1. 点iから(i+1)、(i+2)、…、Nにすべて到達可能である。
2. 点iから点jに到達するとき、j-i<=Kなら、たどる辺の数はj-i本
3. 点iから点jに到達するとき、j-i>Kなら、たどる辺の数はj-i本またはj-i-K本のいずれか

元のグラフに辺を足して上記条件を満たすとき、そのようなグラフの数を求めよ。

解法

• 条件1,2より、点i→点(i+1)はすべて辺を張らなければならない。
• 条件3より、点a→点a+K+1、すなわち1手で(K+1)個分点を進めるようなショートカット辺を張ることができる。ただし、そのような辺は２回以上通れてはいけない。
• 上記２種類以外の辺は張ってはいけない

まず最初に辺を分析し、すでに上記条件を満たさないなら答えは0である。

初期状態でショートカット辺が１つもないなら、任意のP→(P+K+1)に対し(P+1)～(P+K)を開始点とするショートカット辺を張れるので、(2^K)を加算する。（ただし終点がNを超えないようにする)

初期状態でショートカット辺があるなら、既存のショートカット辺と合わせ２回以上通れないようにショートカット辺の配置していき、同様にショートカット辺の数Kに対し(2^K)を加算する。

int N,M,K;
map<int,int> R;
int S[1000001];

// a^n % p
ll modpow(ll a, ll n, ll p) {
	ll r=1;
	while(n) {
		if(n%2) r=(r*a)%p;
		a=(a*a)%p;
		n>>=1;
	}
	return r;
}

void solve() {
	int f,r,i,j,k,l, x,y,ma,nt;
	int kl=-1,kr=-1;
	cin>>N>>M>>K;
	ll d1=0,dk=0;
	
	FOR(i,M) {
		x=GETi()-1;
		y=GETi()-1;
		if(y-x==1) continue;
		if(y-x!=K+1) {
			_P("0\n");
			return;
		}
		
		if(dk==0) kl=x;
		kr=x;
		S[x]=1;
		if(kl+K<x) {
			_P("0\n");
			return;
		}
		dk++;
	}
	
	N-=(K+1);
	if(dk==0) {
		R[0]++;
		FOR(i,N) R[min(K,N-1-i)]++;
	}
	else {
		for(i=max(0,kr-K);i<kl;i++) R[min(K,N-(i+1))-dk]++;
		R[min(K,N-(i+1))-(dk-1)]++;
	}
	
	ll res=0;
	ITR(it,R) res = (res + it->second * modpow(2,it->first,1000000007)) % 1000000007;
	
	cout << res << endl;
	return;
}

まとめ

こういう問題を思いつくセンスがいいな。