Dyd's Blog

He who has a strong enough why can bear almost any how.

luoguP4892 GodFly的寻宝之旅

Posted on Edited on In
Symbols count in article: 2.6k Reading time ≈ 2 mins.

随机跳题都给我跳些神马玩意

GodFly的寻宝之旅

看了数据范围，感觉 $m$ （边数）应该只是做权值的，时间应和 $n$ 关系大些（毕竟 $n \le 18, m \le 10^5$ ），先考虑了暴力，暴搜走法，以边数为权值，时间复杂度为 $O(n!)$ 期望30分（我也没打所以正确性没保证）

然后继续以 $m$ 为权值的思路，考虑状压dp，设 $f[i][j][w]$ 表示“走到点 $i$ ，当前点集合为 $j$ 且当前代价为 $w$ 的方案数”，转移很显然，下面以 $w = 0$ 的转移为例：
$$
\begin{align}
&\text{设当前地图为}j \text{（不存在}v \text{），和为}sum(j) \text{且存在边}u \rightarrow v \text{数为}mp[u][v] \text{，} j + v \text{指将点}v \text{压入状态}\\
&f[v][j + v][0] += mp[u][v] *
\begin{cases}
f[u][j][0] & if(v \mod 2 = 0)\\
f[u][j][0] & if(v \mod 2 = 1 \wedge sum(j) \mod 2 = 0)\\
f[u][j][1] & if(v \mod 2 = 1 \wedge sum(j) \mod 2 = 1)
\end{cases}
\end{align}
$$
打的很快，注意了取模，结果一交——WA

想对着样例调一下，于是翻出了2018的比赛（这是那次比赛的第三题），正打算下载样例，结果……谁家出题组样例用百度网盘发呀！下一个百度网盘太麻烦，于是放弃，只好对着死调

就在我万念俱灰之时，突然感觉 $f[i][j][w]$ 的顺序怪怪的，因为dp的无后效性是用第二维（当前点集只增不减）来保证的，那么是不是应该先枚举 $j$ 再枚举 $i$ 呢？怀着如果还不过就只有手造样例心态，把第二层循环调到了最外层，结果，柳暗花明又一村，AC了！

代码

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
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 20, P = 19260817, D = (1 << 18);
int n, m;
int mp[N][N];
int f[N][D][2]; //f[i][j][w]:走到i,当前点集为j,价值为w的方案数
int have(int x, int y)
{
	return ((x >> (y - 1)) & 1);
}
int add(int x, int y)
{
	return (x | (1 << (y - 1)));
}
int get_s(int x)
{
	int res = 0;
	for (int i = 1; i <= n; ++i)
		if (have(x, i))
			res += i;
	return res;
}
void see(int x) //debug
{
	cout << endl;
	cout << x << " have" << endl;
	for (int i = 1; i <= n; ++i)
		if (have(x, i))
			cout << i << " ";
	cout << endl;
}
int main()
{
	int c, d;
	scanf("%d%d", &n, &m);
	d = (1 << n) - 1;
	for (int i = 1, u, v; i <= m; ++i)
	{
		scanf("%d%d", &u, &v);
		++mp[u][v], ++mp[v][u];
	}
	for (int i = 1; i <= n; ++i) //每个点只走一次,故没有自环
		mp[i][i] = 0;
	f[1][1][0] = 1;
	for (int j = 1, sum; j <= d; ++j) //将第二层循环移到最外
	{
		sum = get_s(j);
		for (int i = 1; i < n; ++i) //到n就停止,故不可能从n走到其它点
		{
			if (!have(j, i))
				continue;
			for (int k = 1; k <= n; ++k)
			{
				if (have(j, k))
					continue;
				if (!mp[i][k])
					continue;
				if (k & 1)
				{
					if (sum & 1)
					{
						f[k][add(j, k)][1] = ((LL)f[i][j][0] * mp[i][k] % P + f[k][add(j, k)][1]) % P;
						f[k][add(j, k)][0] = ((LL)f[i][j][1] * mp[i][k] % P + f[k][add(j, k)][0]) % P;
					}
					else
					{
						f[k][add(j, k)][1] = ((LL)f[i][j][1] * mp[i][k] % P + f[k][add(j, k)][1]) % P;
						f[k][add(j, k)][0] = ((LL)f[i][j][0] * mp[i][k] % P + f[k][add(j, k)][0]) % P;
					}
				}
				else
				{
					f[k][add(j, k)][1] = ((LL)f[i][j][1] * mp[i][k] % P + f[k][add(j, k)][1]) % P;
					f[k][add(j, k)][0] = ((LL)f[i][j][0] * mp[i][k] % P + f[k][add(j, k)][0]) % P;
				}
			}
		}
	}
	scanf("%d", &c);
	int ans = 0;
	for (int i = 1; i <= d; ++i)
		ans = (ans + f[n][i][c]) % P;
	printf("%d\n", ans);
	return 0;
}

感觉这个状压比较简单，毕竟连我这种奆弱都可以做

说句题外话，找样例的时候虽然样例没找到，但发现GodFly是“牛虻”的意思