Loj 2540 随机算法

Posted on | Edited on | Views:

状压 dp.

由于图的点数比较少,所以可以先 $O(2^n)$ 把真实的最大独立集大小给算出来,然后算有几个集合使得答案等于它.

设 $dp(S,i)$ 表示当前排列中已经加入的元素集合为 $S$ ,算出的独立集大小为 $i$ 的方案数.

转移时,考虑将一个点 $x$ 加入独立集中,记 $x$ 以及它所有邻居构成的集合为 $T$ .

那么 $x$ 必须是 $T-S$ 中第一个出现的元素,转移有
$$
dp(S\cup T,i+1)\leftarrow dp(S,i)\cdot A_{n-|S|}^{|T-S|}\cdot \frac{1}{|T-S|}
$$

$T-S$ 表示 $S$ 在 $T$ 中的相对补集,即在集合 $T$ 中,但不在集合 $S$ 中的所有元素构成的集合.

时间复杂度 $O(m+2^n\cdot n)$ .

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out = 0, fh = 1;
	char jp = getchar();
	while ((jp > '9' || jp < '0') && jp != '-')
		jp = getchar();
	if (jp == '-')
		fh = -1, jp = getchar();
	while (jp >= '0' && jp <= '9')
		out = out * 10 + jp - '0', jp = getchar();
	return out * fh;
}
void print(int x)
{
	if (x >= 10)
		print(x / 10);
	putchar('0' + x % 10);
}
void write(int x, char c)
{
	if (x < 0)
		putchar('-'), x = -x;
	print(x);
	putchar(c);
}
const int P = 998244353;
int add(int a, int b)
{
	return a + b >= P ? a + b - P : a + b;
}
void inc(int &a, int b)
{
	a = add(a, b);
}
int mul(int a, int b)
{
	return 1LL * a * b % P;
}
int fpow(int a, int b)
{
	int res = 1;
	while (b)
	{
		if (b & 1)
			res = mul(res, a);
		a = mul(a, a);
		b >>= 1;
	}
	return res % P;
}
const int N = 20;
int n, m, popc[1 << N], dp[1 << N][N + 1], nxt[N], mx;
int fac[N + 1], invfac[N + 1];
int A(int x, int y)
{
	return mul(fac[x], invfac[x - y]);
}
int main()
{
	n = read(), m = read();
	fac[0] = 1;
	for (int i = 1; i <= n; ++i)
		fac[i] = mul(fac[i - 1], i);
	invfac[n] = fpow(fac[n], P - 2);
	for (int i = n - 1; i >= 0; --i)
		invfac[i] = mul(invfac[i + 1], i + 1);
	for (int i = 1; i <= m; ++i)
	{
		int u = read() - 1, v = read() - 1;
		nxt[u] |= 1 << v;
		nxt[v] |= 1 << u;
	}
	for (int i = 0; i < n; ++i)
		nxt[i] |= 1 << i;
	for (int S = 1; S < (1 << n); ++S)
	{
		popc[S] = popc[S >> 1] + (S & 1);
		bool f = true;
		for (int i = 0; i < n && f; ++i)
			if (S >> i & 1)
				f &= (popc[S & nxt[i]] == 1);
		if (f)
			mx = max(mx, popc[S]);
	}
	dp[0][0] = 1;
	for (int S = 0; S < (1 << n); ++S)
		for (int i = 0; i < mx; ++i) if (dp[S][i])
			for (int x = 0; x < n; ++x)
				if (!(S >> x & 1))
				{
					int T = nxt[x];
					int c = A(n - popc[S] - 1, popc[T] - popc[T & S] - 1);
					inc(dp[S | T][i + 1], mul(dp[S][i], c));
				}
	int ans = mul(dp[(1 << n) - 1][mx], invfac[n]);
	write(ans, '\n');
	return 0;
}