「考试总结」2023-02-13 联合省选模拟赛 – Day1

爆搜 $ \texttt {(dfs)} $

$ \texttt {Statement} $

给定一个 $ n $ 个点 $ m $ 条边的简单无向图，你需要对所有匹配 $ S $，把 $ c ^ { | S | } $ 求和，其中 $ | S | $ 是匹配的大小。对 $ 10 ^ 9 + 7 $ 取模。

一个匹配就是一个可以为空的边集，使得每个点至多是其中一条边的端点。

$ 1 \leq n \leq 36 $ ，$ 0 \leq m \leq \dfrac { n ( n - 1 ) } 2 $ ，$ 1 \leq c \leq 10 ^ 9 + 6 $

$ \texttt {Solution} $

新增一个零度的点是不会对答案造成影响的，因此可以加点使 $ n $ 为偶数，并且默认点的标号为 $ 0 \sim ( n - 1 ) $。

记匹配中的边为实边，在 点 $ 2 i $ 和 点 $ 2 i + 1 $ 之间连一条虚边，得到新匹配。
因为 每个点至多是其中一条边的端点，所以连上虚边之后每个点的度数不超过 $ 2 $。
因此对于一个连通块，它只可能是一条链或者一个简单环。
那么对于新匹配，就是若干条链和若干个环组成的简单图。

显然新匹配和原匹配是一一对应的。
考虑在新匹配拆成若干个连通块 $ \texttt {dp} $，再把每个连通块拼起来。
一个连通块再分成链和环两种情况计算。

巧妙之处在于通过连虚边的方式转换问题，而新问题中 $ 2i $ 和 $ 2i + 1 $ 一定是相连的，这样枚举点集的状态数就可以压缩至 $ 2 ^ { 0.5 n } \leq 2 ^ {18} $ 个了，比纯 $ \texttt { dp } $ 优化了很多。

计算环的方法与 $ \texttt {「CF11D」A Simple Task} $ 类似，注意下 $ 2i $ 和 $ 2i + 1 $ 是相连的即可。

这里只讲计算链的方法。

定义 $ f_{ s, i } $ 表示当前走过的点集为 $ s $，现在的终点为 $ i $ 的方案数。
枚举不在集合 $ s $ 中的点 $ j $，如果 $ i $ 和 $ j $ 之间实边相连，那么 $ f_{ t, j \texttt{ xor } 1 } \gets f_{ s, i } $，其中 $ t $ 表示 $ s $ 的集合中加入点 $ j $ 得到的新集合。$ j \texttt { xor } 1 $ 是因为点 $ j $ 与点 $ j \texttt { xor } 1 $ 之间一定有边相连，判断的是 $ i $ 和 $ j $，新的终点就是 $ j \texttt { xor } 1 $。

$ \texttt {Code} $

#include <cstdio>

#define LL long long
#define uLL unsigned LL

namespace Read {
	static const int buf_size = 1 << 12;
	static const bool use_fread = true;
	
	static unsigned char buf[buf_size];
	static int buf_len, buf_pos;
	
	bool isEOF() {
		if (buf_pos == buf_len) {
			buf_pos = 0; buf_len = fread(buf, 1, buf_size, stdin);
			if (buf_pos == buf_len) return true;
		}
		return false;
	}
	
	char readChar() {
		if (!use_fread) return getchar();
		return isEOF() ? EOF : buf[buf_pos++];
	}
	
	LL rint() {
		LL x = 0, Fx = 1; char c = readChar();
		while (c < '0' || c > '9') { Fx ^= (c == '-'); c = readChar(); }
		while ('0' <= c && c <= '9') { x = (x << 3) + (x << 1) + (c ^ 48); c = readChar(); }
		return Fx ? x : -x;
	}
	
	template <typename T>
	void read(T &x) {
		x = rint(); 
	}
	
	template <typename T, typename... Ts>
	void read(T &x, Ts &...rest) {
		read(x);
		read(rest...);
	}
} using namespace Read;

namespace Math {
	LL Max(LL u, LL v) { return (u > v) ? u : v; }
	LL Min(LL u, LL v) { return (u < v) ? u : v; }
} using namespace Math;

const int mod = 1e9 + 7;
const int inv = (mod + 1) >> 1;

const int MAX_n = 36;
const int MAX_m = 630;

const int mx = 1 << 18;

int n, m, c, up;

int qpow[MAX_n + 5];

int dp[mx + 5][MAX_n + 5];
int dpp[mx + 5][MAX_n + 5];

int dp1[mx + 5], dp2[mx + 5];

bool vis[MAX_n + 5][MAX_n + 5];

int main() {
	freopen("dfs.in", "r", stdin);
	freopen("dfs.out", "w", stdout);
	read(n, m, c); n += (n & 1); up = 1 << (n >>= 1);
	for (int i = 1, u, v; i <= m; i++)
		read(u, v), --u, --v, vis[u][v] = vis[v][u] = true;
	qpow[0] = 1 % mod;
	for (int i = 1; i <= n; i++)
		qpow[i] = (LL)qpow[i - 1] * c % mod;
	for (int i = 0; i < n; i++) {
		dp[1 << i][i << 1] = dp[1 << i][i << 1 | 1] = 1;
		dpp[1 << i][i << 1 | 1] = 1;
	}
	for (int S = 1; S < up; S++) {
		int siz = 0, id = 0;
		for (int i = 0; i < n; i++)
			if (S & (1 << i)) ++siz;
		for (int i = 0; i < n; i++) {
			if (S & (1 << i)) {
				int a = i << 1, b = i << 1 | 1;
				for (int j = 0; j < n; j++) {
					if (S & (1 << j)) continue;
					int x = j << 1, y = j << 1 | 1, T = S | (1 << j);
					if (vis[a][x]) dp[T][y] = (dp[T][y] + dp[S][a]) % mod;
					if (vis[a][y]) dp[T][x] = (dp[T][x] + dp[S][a]) % mod;
					if (vis[b][x]) dp[T][y] = (dp[T][y] + dp[S][b]) % mod;
					if (vis[b][y]) dp[T][x] = (dp[T][x] + dp[S][b]) % mod;
				}
			}
		}
		for (int i = 0; i < n; i++)
			if (S & (1 << i)) { id = i; break; }
		for (int i = id; i < n; i++) {
			if (S & (1 << i)) {
				int a = i << 1, b = i << 1 | 1;
				for (int j = id + 1; j < n; j++) {
					if (S & (1 << j)) continue;
					int x = j << 1, y = j << 1 | 1, T = S | (1 << j);
					if (vis[a][x]) dpp[T][y] = (dpp[T][y] + dpp[S][a]) % mod;
					if (vis[a][y]) dpp[T][x] = (dpp[T][x] + dpp[S][a]) % mod;
					if (vis[b][x]) dpp[T][y] = (dpp[T][y] + dpp[S][b]) % mod;
					if (vis[b][y]) dpp[T][x] = (dpp[T][x] + dpp[S][b]) % mod;
				}
			}
		}
		for (int j = 0; j < n; j++) {
			if (S & (1 << j)) {
				int x = j << 1, y = j << 1 | 1;
				dp1[S] = (dp1[S] + (LL)dp[S][x] * qpow[siz - 1] % mod * inv) % mod;
				dp1[S] = (dp1[S] + (LL)dp[S][y] * qpow[siz - 1] % mod * inv) % mod;
			}
		}
		for (int j = id; j < n; j++) {
			if (S & (1 << j)) {
				int x = j << 1, y = j << 1 | 1;
				if (vis[x][id << 1]) dp1[S] = (dp1[S] + (LL)dpp[S][x] * qpow[siz]) % mod;
				if (vis[y][id << 1]) dp1[S] = (dp1[S] + (LL)dpp[S][y] * qpow[siz]) % mod;
			}
		}
	}
	dp2[0] = 1 % mod;
	for (int S = 1; S < up; S++) {
		int siz = 0, id = 0;
		for (int i = 0; i < n; i++)
			if (S & (1 << i)) ++siz, id = i;
		for (int T = S; T & (1 << id); T = (S & (T - 1)))
			dp2[S] = (dp2[S] + (LL)dp2[S ^ T] * dp1[T]) % mod;
	}
	printf("%d\n", dp2[up - 1]);
	return 0;
}