ABC306H 题解

First Post:

Last Update:

集合划分容斥练手题。

首先要注意到这是一个类似 DAG 定向的模型。实际上，如果没有 "=" 的情况，这就是经典的 DAG 定向问题。

先考虑没有 "=" 怎么做。设 表示将点集 的导出子图定向为 DAG 的方案数。

考虑按层构建出一个 DAG，也就是说，我们枚举 表示 中入度为 的点集，从 转移到 。那么在 与 之间的边，方向显然是从 连到 。转移条件也显然， 必须是个独立集。

但直接这么枚举肯定会算重，毕竟这个 “入度为 的点集“ 并不是极大的。

但这里去重的手段很有限，最好的办法就是配凑容斥系数了。

我们希望对每个集合 赋一个容斥系数 ，使得每个 “极大的入度为 的点集” 的系数和为 。

设 对应的集合幂级数为 。

那一个极大的点集 的系数和是什么呢？是 。

我们希望 ，其中 的每一项均为 。

计算集合幂级数的逆可以得到 。

那么从 转移到 时，乘上 的系数即可。

回到原问题。

现在我们仍然尝试枚举“入度为 的点集” ，此时 "=" 的边不算在入度中。

我们之前限制 必须是个独立集，但现在 中可以有边了，只不过所有边都得是 "="。

所以将 "=" 号形成的连通块缩点，设连通块个数为 ，那这个点集 实际上等效于没有 "=" 的情况中一个大小为 的点集，所以给 一个 的容斥系数即可。

暴力 DP 转移是 的，使用集合幂级数求逆可以做到 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
using namespace std;
const int N = 18,Sz = 1 << 17,M = 400,P = 998244353;
inline void Plus(int &x,const int &y) { x += y;if(x >= P) x -= P;}
inline int qpow(int a,int b) { int res = 1;while(b) {if(b&1) res = 1ll * res * a % P;a = 1ll * a * a % P;b >>= 1;} return res;}
int n,m;
int U[M],V[M];

inline void GetInv(int *f,int *g,int n) {
	int finv = g[0] = qpow(f[0],P - 2);
	for(int i = 1;i < n;i++) {
		int res = 0;
		for(int j = 1;j <= i;j++)
			Plus(res,P - 1ll * f[j] * g[i - j] % P);
		g[i] = 1ll * res * finv % P;
	}
}
inline void FWT(int *F,int len,int op) {
	for(int k = 1;k < len;k <<= 1)
		for(int j = 0;j < len;j += k + k)
			for(int i = 0;i < k;i++)
				if(op == 1) Plus(F[i | j | k],F[i | j]);
				else Plus(F[i | j | k],P - F[i | j]);
}
int siz[Sz];
int fa[N];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]);}
inline void Merge(int x,int y) { fa[find(x)] = find(y);}
inline int Getcoef(int S) {
	for(int i = 0;i < n;i++) fa[i] = i;
	for(int i = 1;i <= m;i++)
		if((S >> U[i] & 1) && (S >> V[i] & 1))
			Merge(U[i],V[i]);
	int res = 1;
	for(int i = 0;i < n;i++)
		if((S >> i & 1) && find(i) == i) 
			++res;
	// res = 0;
	return (res & 1) ? P - 1 : 1;
}
int f[N][Sz];
int dp[Sz];
int main() {
	cin >> n >> m;
	for(int i = 1;i <= m;i++) 
		cin >> U[i] >> V[i],--U[i],--V[i];
	int all = 1 << n;
	for(int i = 1;i < all;i++)
		siz[i] = siz[i >> 1] + (i&1);
	for(int i = 1;i < all;i++)
		f[siz[i]][i] = Getcoef(i);
	// dp[0] = 1;
	// for(int S = 1;S < all;++S)
	// 	for(int T = S;T;T = (T - 1) & S)
	// 		Plus(dp[S],1ll * f[siz[T]][T] * dp[S - T] % P);
	// cout << dp[all - 1] << endl;
	f[0][0] = 1;
	for(int i = 1;i < all;i++) f[siz[i]][i] = P - f[siz[i]][i];
	for(int i = 0;i <= n;i++)
		FWT(f[i],all,1);
	for(int t = 0;t < all;t++) {
		static int g[N],h[N];
		for(int i = 0;i <= n;i++)
			g[i] = f[i][t];
		GetInv(g,h,n + 1);
		for(int i = 0;i <= n;i++)
			f[i][t] = h[i];
	}
	for(int i = 0;i <= n;i++)
		FWT(f[i],all,-1);
	cout << f[n][all - 1] << endl;
	return 0;
}

≡