枚举连通块拆贡献+容斥：ABC321G

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133266690

https://atcoder.jp/contests/abc321/tasks/abc321_g

这种题都没看出来我要去退役了

看完题目，可以获得：

  1. 期望、连通块：显然拆贡献啊！

  2. n≤17n\le 17 ：这不明显状压？结合前面连通块，就是枚举连通块啊！

  3. 继续分析第2点，17这么小，显然枚举子集。为啥枚举？计数题只有容斥这个套路啊！

然后就很裸了。

为啥容斥？因为拆完贡献后要使得 恰好 为一个连通块。

这里还有个小套路。容斥是为了不重不漏，我们可以枚举最编号小点所在的 单个 连通块。剩下随便连。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
n=read(); m=read(); init(m); 
for(i=1; i<=m; ++i) k=read(), R[1<<k-1]++; 
for(i=1; i<=m; ++i) k=read(), B[1<<k-1]++; 
for(s=1; s<(1<<n); ++s) {
	for(i=1; i<=n; ++i) if(s&(1<<i-1)) break; 
	R[s]=R[s-(1<<i-1)]+R[1<<i-1]; 
	B[s]=B[s-(1<<i-1)]+B[1<<i-1]; 
	if(R[s]==B[s]) {
		f[s]=g[s]=fac[R[s]]; 
		for(t=(s-1)&s; t; t=(t-1)&s) 
			if(t&(1<<i-1)) Add(g[s], -g[t]*f[s-t]); 
		Add(ans, g[s]*fac[m-R[s]]); 
	}
}
ans=(ans*ifac[m]%mo+mo)%mo; 
printf("%lld", ans);