今回変則的過ぎて、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か…」と迷ってしまった。