TopCoder SRM 756 Div1 Hard Newgenerations

これHardなの意外。
https://community.topcoder.com/stat?c=problem_statement&pm=15404

問題

H*Wのグリッドが与えられる。
セルの属性は以下のいずれかである。

• active
• inactive
• activeかinactiveか不明
• special (specialなセルはactiveでもある)

隣接するactiveセル間に辺を張るものとする。
その際、辺を３色のいずれかで彩色する。
activeかinactiveか不明なセルをどちらかにしたとき、specialなセルとつながる辺に同色の物がないような組み合わせは何通りか。

解法

specialなセルに隣接セルが4つあると鳩ノ巣原理で同色の辺が2本以上できてしまう。
一方3つ以下なら必ずそうならないように彩色できるらしい。

よって、隣接セルが4つ来ない組み合わせを列挙しよう。
specialなセルは20個しかないので、包除原理で求めよう。
隣接セルが４つ来るspecialセルが決まっていれば、その隣接セルはactiveでなければならず、残りはどうでもよい。

ll mo=1000000007;
ll p2[5050];
vector<int> L;

class Newgenerations {
	public:
	int count(vector <string> S) {
		int H=S.size(),W=S[0].size();
		vector<vector<int>> V;
		int x,y,i,j;
		int numf=0;
		
		p2[0]=1;
		FOR(x,5000) p2[x+1]=p2[x]*2%mo;
		
		FOR(y,H) FOR(x,W) {
			if(S[y][x]=='x') {
				S[y][x]='#';
				V.push_back({y,x});
			}
			if(S[y][x]=='*') numf++;
		}
		ll ret=0;
		int N=V.size(),mask;
		FOR(mask,1<<N) {
			int NG=0;
			L.clear();
			FOR(i,N) if(mask&(1<<i)) {
				FOR(j,4) {
					int dd[4]={1,0,-1,0};
					int ty=V[i][0]+dd[j];
					int tx=V[i][1]+dd[j^1];
					if(ty<0 || ty>=H || tx<0 || tx>=W) {
						NG=1;
					}
					else if(S[ty][tx]=='.') {
						NG=1;
					}
					else if(S[ty][tx]=='*') {
						L.push_back(ty*50+tx);
					}
				}
			}
			if(NG) continue;
			sort(ALL(L));
			L.erase(unique(ALL(L)),L.end());
			if(__builtin_popcount(mask)%2==0) {
				ret+=p2[numf-L.size()];
			}
			else {
				ret+=mo-p2[numf-L.size()];
			}
		}
		return ret%mo;
	}
}

まとめ

真面目に証明しようとすると大変？