AtCoder ABC #220 : H - Security Camera

うーむ。
https://atcoder.jp/contests/abc220/tasks/abc220_h

問題

N点M辺のグラフが与えられる。
N点のうちいくつかを選択することを考えると、その選び方は2^N通りある。
この時、M辺のうち、両端の少なくとも片方が選択済み頂点となるようなものが偶数本となるのは何通りか。

解法

Nの上限が40なので、半分全列挙しよう。
そこで頂点を2つの集合S,Tに分割する。

Sの部分集合s、Tの部分集合tに対し、以下を定める。
L(s) := sによって条件を満たす辺の数の偶奇(0/1)
C(s) := Tのうち、(S/s)に対し奇数本の辺を持つような頂点tの集合
R(t) := tの誘導部分グラフの辺の数の偶奇(0/1)

とすると、sに対し
L(s) xor (popcount(C(s)∩t)%2) xor R(t) = 0
となるtが条件を満たす。

そこで、
f(t') = (popcount(t'∩t)%2) xor R(t)が0となるtの数
を求めておけば、sに対し

• L(s)が0ならf(C(s))
• L(s)が1なら2^|T|-f(C(s))

を解に計上すればよくなる。あとはf(t')を求めよう。これはR(t)から畳み込み演算の要領で求めることができる。

int N,M;
ll E[40];
int dp[1<<20];

void dfs(int L,int R,int d) {
	if(d==0) return;
	int M=(R+L)/2;
	dfs(L,M,d-1);
	dfs(M,R,d-1);
	int i;
	FOR(i,M-L) {
		int a=dp[L+i], b=dp[M+i];
		dp[L+i]=a+b;
		dp[M+i]=a+(R-M)-b;
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		x--,y--;
		E[x] |= 1LL<<y;
		E[y] |= 1LL<<x;
	}
	int mask;
	
	FOR(mask,1<<20) {
		int num=0;
		FOR(y,20) FOR(x,y) if(E[x+20]&(1LL<<(y+20))) if(mask&((1<<x)|(1<<y))) num^=1;
		dp[mask]=num;
	}
	
	dfs(0,1<<20,20);
	
	ll ret=0;
	FOR(mask,1<<20) {
		int num=0;
		int cut=((1<<20)-1)^mask;
		FOR(y,20) FOR(x,y) if(E[x]&(1<<y)) if(mask&((1<<x)|(1<<y))) num^=1;
		FOR(x,20) if(mask&(1<<x)) FOR(y,20) if(E[x]&(1LL<<(y+20))) num^=1;
		
		int Tmask=0;
		FOR(i,20) if(__builtin_popcountll(cut&E[i+20])%2==1) Tmask |= 1<<i;
		
		if(num==0) ret+=(1<<20)-dp[Tmask];
		else ret+=dp[Tmask];
	}
	
	assert((ret&((1LL<<(40-N))-1))==0);
	
	ret>>=(40-N);
	cout<<ret<<endl;
	
}

まとめ

うーむ、これはしんどい。