Security Camera [ABC220H]

https://atcoder.jp/contests/abc220/tasks/abc220_h

题解

考虑折半搜索，将 \(n\) 个点分为大小为 \(\dfrac{n}{2}\) 的两个集合 \(S, T\)

设 \(F1[s]\ (s\subseteq S)\) 表示如果选了 \(s\) 中的点安装摄像头，那么被监视的边的数量的奇偶性

设 \(F2[t]\ (t\subseteq T)\) 表示如果选了 \(t\) 中的点安装摄像头，那么被监视的两端都在 \(T\) 中的边的数量的奇偶性

设 \(G[s]\ (s\subseteq S)\) 表示所有 (和 \(\{S\) \ \(s\}\) 中的点之间有奇数条边的) 的 \(T\) 中的点的集合

以上都可以在 \(O(n*2^{\frac{n}{2}})\) 的时间内计算

那么一对 \(s,t\) 满足题目条件当且仅当：

\[F1[s] \oplus F2[t] \oplus \ (\operatorname{popcount}(G[s]\& T)\&1) = 0 \]

考虑如何计数

枚举 \(G[s]\& T\)，考虑计算

\[H[P][0/1] = \sum\limits_{G[s]\& T = P} [F1[s]\oplus F2[t] = 0/1] \]

\[Ans=\sum\limits_{P\subseteq T} H[P][\operatorname{popcount}(P)] \]

发现上面第一个式子长得像个集合交卷积

枚举 \(v1=0/1, v2=0/1\)，计算 \(C1[P]=\sum\limits_{G[s]=P} [F1[s]=v1], C2[P]=[F2[P]=v2]\)，

那么 \(H[P][v1\oplus v2] = \sum\limits_{s\& t = P} C1[s]*C2[t]\)

使用 \(FWT\) 在 \(O(n*2^{\frac{n}{2}})\) 的时间内计算

代码

#include 
#define N 50
#define M (1<<20)+5
#define pb push_back
#define lb(x) (x&-x)
using namespace std;
typedef long long ll;

int n, m, G[M], cnt[M]; 
bool F1[M], F2[M];
ll C1[M], C2[M];
vector E[N];
inline int chk(int s, int x) { return (s>>x)&1; }

void FWT(ll *F, int _n, int tp) {
	for (int i = 1; i < (1<<_n); i <<= 1) {
		for (int j = 0; j < (1<<_n); j += i+i) for (int k = 0; k < i; k++) {
			F[j+k] += tp*F[i+j+k];  
		}
	}
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1, u, v; i <= m; i++) {
		scanf("%d %d", &u, &v); 
		E[u].pb(v); E[v].pb(u);
	}
	int t1 = n/2, t2 = n-t1;
	for (int s = 1; s < (1<t1) F1[s]^=1;
			if (y > t1) G[s] ^= (1<<(y-t1-1));
		}
	}
	for (int s = 1; s < (1< t1 && !chk(s,y-t1-1)) F2[s]^=1;
		}
	}
	ll ans = 0; int mx = (1<