kmjp's blog

競技プログラミング参加記です

TopCoder SRM 804 : Div1 Medium UnluckyNumber

今回変則的過ぎて、500ptの難易度が普段のDiv1と同じかよくわからんな。
https://community.topcoder.com/stat?c=problem_statement&pm=16402&rd=18642

問題

N頂点M辺のグラフが与えられる。

ここで、頂点に対応してN要素の整数列Aを考える。
各値は1~Kのいずれかを取ることができる。
ただし、元のグラフで辺がある頂点間に対応する要素同士は、和がZになってはならない。

条件を満たすのは何通りか。

解法

Mが最大18と小さいので、包除原理で解く。
Mの部分集合に対し、それらの辺に対応する頂点間に対応する要素同士はすべて和がZとなるケースを数え上げよう。

連結成分毎に見て、

  • 1要素だけの連結成分は、1~Kのどれでもよい
  • 奇数長の閉路を持つ連結成分は、Zが偶数なら全要素Z/2しか条件を満たさない。奇数ならそもそも条件を満たさない。
  • 2要素以上で二部グラフの場合、片方のグループをa、もう片方をZ-aとするケースを考えると、aの取りえる値がわかる。

あとは部分集合の要素数に応じて、組み合わせを足し引きするだけ。

vector<int> E[20];
const ll mo=1000000007;
int vis[20];

class UnluckyNumber {
	public:
	
	int dfs(int cur,int col) {
		if(vis[cur]!=-1) {
			return col!=vis[cur];
		}
		vis[cur]=col;
		int ret=0;
		FORR(e,E[cur]) ret|=dfs(e,col^1);
		return ret;
	}
	
	int numberOfColourings(int n, int m, int k, int z, vector <int> x, vector <int> y) {
		ZERO(E);
		
		int i;
		ll ret=0;
		int mask;
		FOR(mask,1<<m) {
			FOR(i,n) E[i].clear(), vis[i]=-1;
			FOR(i,m) if(mask&(1<<i)) {
				E[x[i]-1].push_back(y[i]-1);
				E[y[i]-1].push_back(x[i]-1);
			}
			ll pat=1;
			FOR(i,n) if(vis[i]==-1) {
				if(E[i].size()==0) {
					pat=pat*k%mo;
				}
				else if(dfs(i,0)) {
					if(z%2) pat=0;
				}
				else {
					if(z<=k+1) pat=pat*(z-1)%mo;
					else pat=pat*(2*k+1-z)%mo;
					
				}
			}
			
			if(__builtin_popcount(mask)%2) {
				ret+=mo-pat;
			}
			else {
				ret+=pat;
			}
		}
		return ret%mo;
		
		
		
	}
}

まとめ

最初Nだけ目に入って、「Mは最大18*17/2か…」と迷ってしまった。