LOJ #2540. 「PKUWC2018」随机算法

题目地址：[呀，戳轻点qwq](https://loj.ac/problem/2540)

一开始自己就想错了，本来以为只要选择的点集定了，那么覆盖状态也就定了。
但是发现并不对，和点选择的顺序还有关。
……
我们去$Orz$题解吧。
发现问题仍然是没有完全理解增量的构造方式。

考虑到选择点的顺序其实是和答案有关的，我们考虑对整个操作序列增量的过程进行$dp$。
设$f(i,S)$表示当前答案为$i$，已经考虑(也就是不能选)的点集为$S$时对应操作序列的个数。
注意，我们所说的考虑的点都是算在了操作序列中，也就是每一个算在$dp$中的操作序列都含有了当前不能选的所有点。
考虑每一次选择一个点$u$加入最大独立集中，我们只要保证$u$点周围没有被选择的点全部选在这个点之后即可。
先预处理出与$u$相邻的点$mask(u)$。
$$f(i,S)(n-|S|-1)^{\underline {|mask(k)-mask(k)\cap S|}}\to f(i+1,S\cup mask(u))$$
表示选一些空位给新点做排列。

虽然已经可以卡过了，但是这样的复杂度是$O(n^22^n)$的。

我们发现其实$i$这维状态没有太大必要，我们可以对每个$S$直接记录它当前的最大独立集大小，最大独立集大小扩大时清空$f$即可。

时间复杂度$O(n2^n)$

```
#include<cstdio>
#include<algorithm>
#include<vector>
#define LL long long
using namespace std;
const int maxn = 20;
const int mod = 998244353;
int dp[(1 << maxn)], mx[1 << maxn];
int bc[(1 << maxn)], best, n, m, now, nmask, ans;
int mask[maxn + 5], u, v, mp[maxn + 5][maxn + 5];

void Add(int &x, const int &a) {
	x += a; if(x >= mod) x -= mod;
}

LL fpow(LL a, int b) {
	LL ans = 1;
	while(b) {
		if(b & 1) ans = a * ans % mod;
		a = a * a % mod, b >>= 1;
	}
	return ans;
}

LL step[maxn + 5], inv[maxn + 5];

void pre(int n) {
	step[0] = inv[0] = 1;
	for(register int i = 1; i <= n; ++i)
		step[i] = step[i - 1] * i % mod;
	inv[n] = fpow(step[n], mod - 2);
	for(register int i = n - 1; i >= 1; --i) 
		inv[i] = inv[i + 1] * (i + 1) % mod;
}

LL P(int n, int m) {
	if (m > n || n < 0 || m < 0) return 0;
	return step[n] * inv[n - m] % mod;
}

int main() {
	scanf("%d%d", &n, &m), pre(21);
	for(register int i = 1; i <= n; ++i) {
		mask[i] |= (1 << i - 1);
	}
	for(register int i = 1; i <= m; ++i) {
		scanf("%d%d", &u, &v);
		mp[u][v] = mp[v][u] = 1;
		mask[u] |= (1 << v - 1);
		mask[v] |= (1 << u - 1);
	}
	for(register int i = 1; i < (1 << n); ++i) {
		bc[i] = bc[i >> 1] + (i & 1);
	}
	//for(register int i = 1; i <= n; ++i)
		//dp[mask[i]] = 1, mx[mask[i]] = 1;
	dp[0] = 1;
	for(register int now = 0; now < 1 << n; ++now) {
		if(!dp[now]) continue;
		for(register int k = 1; k <= n; ++k) {
			if(!(now & (1 << k - 1))) {
				nmask = now | mask[k];
				if(mx[nmask] < mx[now] + 1) {
					mx[nmask] = mx[now] + 1;
					dp[nmask] = dp[now] * P(n - bc[now] - 1, bc[mask[k] ^ (mask[k] & now)] - 1) % mod;
				} else 
				if(mx[nmask] == mx[now] + 1)
					Add(dp[nmask], dp[now] * P(n - bc[now] - 1, bc[mask[k] ^ (mask[k] & now)] - 1) % mod);
			}
		}
	}
	printf("%lld", 1ll * dp[(1 << n) - 1] * inv[n] % mod);
	return 0;
}
```

Rockdu's Blog

导航

最近发表

大佬们的友链