自动搬运

查看原文

来自洛谷，原作者为

	ycx303 **

搬运于2025-08-24 22:18:53，当前版本为作者最后更新于2025-03-23 15:16:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P6238 [JSOI2011] 序的计数题解

思路：

首先构建一个新的虚拟节点连接所有目标节点，强行将其作为第一个被访问的节点，这样子就解决了图不连通的问题。

除了目标节点外，所有其他点都可以缩成一个节点。

这样子的图实际上只有 $k + 2$ 个节点， $k + 1$ 个目标节点。

预处理 $G[S][u]$ 表示已经在 dfs 序中出现过的点的集合为 $S$， 当前在点 $u$ 能够访问到的点。

设 $f[S][u]$ 表示当前在点 $u$ ，已经确定 dfs 序的集合为 $S$ 的 dfs 序的方案数。

注意如果一个点和不合法的点有连边，那么这个点不能回朔。

转移的时候枚举一个 $u$ 的相邻点，记忆化搜索即可。

Code：

#include <iostream>
#include <cstdio>
#include <cstring>
#define ll long long
#define MAXN 120
using namespace std;
inline int read() {
	int x = 0;
	bool t = false;
	char ch = getchar();
	while ((ch < '0' || ch > '9') && ch != '-')ch = getchar();
	if (ch == '-')t = true, ch = getchar();
	while (ch <= '9' && ch >= '0')x = x * 10 + ch - 48, ch = getchar();
	return t ? -x : x;
}
int n, m, K, id[MAXN], S[20];
bool g[MAXN][MAXN], M[20][20];
ll f[1 << 19][20];
int G[1 << 19][20];
int dfs(int u, int S) {
	if (~G[S][u])return G[S][u];
	int ret = 1 << u;
	for (int i = 0; i < K; ++i)
		if (M[u][i] && !(S & (1 << i)))ret |= dfs(i, S | (1 << i));
	return G[S][u] = ret;
}
ll Solve(int u, int S) {
	if (~f[S][u])return f[S][u];
	if (G[S][u] == 1 << u)return S == (1 << K) - 1 || !M[u][K];
	ll ret = 0;
	for (int i = 0; i < K; ++i)
		if (M[u][i] && !(S & (1 << i)))
			ret += Solve(i, S | (1 << i)) * Solve(u, S | G[S | (1 << i)][i]);
	return f[S][u] = ret;
}
int main() {
	n = read();
	m = read();
	K = read();
	K += 1;
	for (int i = 1, u, v; i <= m; ++i)u = read(), v = read(), g[u][v] = g[v][u] = 1;
	for (int i = 1; i <= n; ++i)id[i] = K;
	for (int i = 0; i < K - 1; ++i)S[i] = read(), id[S[i]] = i, M[i][K - 1] = M[K - 1][i] = 1;
	for (int i = 0; i <= K; ++i)
		for (int j = 1; j <= n; ++j)M[i][id[j]] |= g[S[i]][j];
	memset(G, -1, sizeof(G));
	memset(f, -1, sizeof(f));
	for (int i = 0; i < (1 << K); ++i)
		for (int j = 0; j < K; ++j)
			if (i & (1 << j))dfs(j, i);
	printf("%lld\n", Solve(K - 1, 1 << (K - 1)));
	return 0;
}