自动搬运

查看原文

来自洛谷，原作者为

	封禁用户 None

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

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

以下是正文

题目链接

简要题面：

有一个无向图（可能不连通），$n$ 个点，$m$ 条边。两个不同点的编号之差不大于 $K$。任意一个点的度数都为偶数（有无度数的点）。对这个无向图的形态进行计数，模 $10^9 + 7$。

$1 \le n,m \le 30$，$1 \le K \le 8$。

思路：

状压 $\texttt{DP}$，计数。很好想的。这一类题的难点其实在不重不漏。

$\texttt{DP}$ 题都是要看性质的。题面其实提示的很清楚了：“任意一个点的度数都为偶数”。显然，出题人希望你通过点的度数的奇偶来推无向图的形态。所以无脑设这题的状态是 $f_{i,j,k}$ 表示 $i$ 个点，$j$ 条边，$k$ 是每个点度数的奇偶（$1$ 是奇数，$0$ 是偶数）。

边界呢？因为当 $i=1$ 时是没有意义的，所以 $i$ 是要从 $2$ 开始的，$1 \to f_{2,0,0}$。

枚举范围呢？“两个不同点的编号之差不大于 $K$”，这句话启示我们让$i-K \sim i-1$ 号点转移到 $i$ 号点。

第 $i$ 位是当前结点，所以每一加一条边度数都会改变，所以 $k \oplus 1 \to k$（状态正着存）。然后改变另一个点的奇偶，即 $k \oplus (2^{i-c}) \to k$（$c$ 为与 $i$ 连边的点）。

可以发现，这样的转移是有序的，每次都由编号大的结点指向编号小的结点。

于是有转移方程：

$f_{i,j,k} = \sum^{i-1}_{c = i-K} {\sum^{2^{K+1}-1}_{a=0}}f_{i,j-1,k \oplus 1 \oplus 2^{i-c}}$

于是某个大聪明打出了这样的代码：

signed main() {
	cin >> n >> m >> k;
	dp[2][0][0] = 1;
	for (int i = 2; i <= n; i++) {
		for (int change = max(1, i - k); change <= i - 1; change++) {
			for (int j = 1; j <= m; j++) {
				for (int now_state = 0; now_state < (1 << (k + 1)); now_state++) {
					dp[i][j][now_state] = (dp[i][j][now_state] + dp[i][j - 1][now_state ^ 1 ^ (1 << i - change)]) % mod;
				}
			}
		}
	}
	cout<<dp[n][m][0]<<'\n';
	return 0;
}

诶，怎么不对呢？怎么都输出 0 啊。形如这样的情况，说明漏了转移。

我们观察到，每一次多一个点的情况都要转移过去，这也是没有讨论全面的一个错误。

添加一个发送式转移至下个阶段：

$f_{i+1,j,k \times 2^{1}} = \sum ^{m}_{j=0} \sum^{2^K-1}_{k = 0}f_{i,j,k}$

坑点：位运算要打括号！取模要小心！

Code:

#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int Data_Range_Of_N = 30 + 5;
const int Data_Range_Of_K = 10 + 5;
int n, m, k;
int dp[Data_Range_Of_N][Data_Range_Of_N][1 << Data_Range_Of_K];
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> k;
	dp[2][0][0] = 1;
	for (int i = 2; i <= n; i++) {
		for (int change = max(1, i - k); change <= i - 1; change++) {
			for (int j = 1; j <= m; j++) {
				for (int now_state = 0; now_state < (1 << (k + 1)); now_state++) {
					dp[i][j][now_state] = (dp[i][j][now_state] + dp[i][j - 1][now_state ^ 1 ^ (1 << i - change)]) % mod;
				}
			}
		}
		for(int j = 0;j<=m;j++) {
			for(int now_state = 0;now_state < (1 << k);now_state++) {
				dp[i+1][j][now_state << 1] = (dp[i][j][now_state] + dp[i+1][j][now_state << 1]) % mod;
			}
		}
	}
	cout<<dp[n][m][0]<<'\n';
	return 0;
}