mydcwfy's Blog

CF1326F2 Wise Men

Posted on
Symbols count in article: 2.4k Reading time ≈ 5 mins.

题意：给定 $n$ 个人两两之间的认识关系，对于一个排列 $p$，设 $s_i$ 表示 $p_i$ 和 $p_{i + 1}$ 的认识关系。问对于每个 $s$ 有多少个 $p$ 能生成该 $s$。$n\leq 18$。

容易发现 $s$ 是长度为 $n - 1$ 的 01 序列。考虑容斥，我们强制钦定了某些位置为 1，剩下的位置随意，那么容易发现原序列被划分成了若干段，每一段内部相邻元素必须相连。容斥完了过后，我们用一个逆高维前缀和的做法就可以在 $O(n 2 ^ n)$ 内解决后半部分。

然后考虑如何计算。对于一段内部，我们使用预处理状压 DP 的做法，记录 $f(i, s)$ 表示已经选了 $s$ 集合，最后一个是 $i$ 的方案数，转移平凡，此部分预处理 DP 是 $O(2 ^ n n ^ 2)$。然后考虑已经枚举完分段过后怎么做。我们本质上是将不同段的状压值子集卷积起来，但是容易发现我们已经知道了每一段分别的 popcount，那么我们最后求 $[x ^ {2 ^ n - 1}]$ 相当于直接或卷积。我们还可以预处理每一段高维前缀和后的值，并且可以在 $O(2 ^ n)$ 时间内部得到一个数组逆高维前缀和过后某一项的值，所以只需要把所有不同段的 DP 并高位前置和后的值乘起来，所有逆高维前缀和得到一项的值即可。直接枚举所有拆分的话复杂度就是 $O(4 ^ n)$ 的。

上述复杂度仍然不能接受，我们发现这个 DP 值仅和所有段长度的 std::multiset 有关，所以这个本质是一个拆分数。于是我们枚举强制钦定的部分就是 $O(p(n))$ 的，而 $p(18) = 385$ 是可以接受的。

于是总复杂度是 $O((p(n) + n ^ 2)2 ^ n)$，可以通过。

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
int getsta()
{
	int s = 0;
	for (int i = 1; i <= tot; ++ i) s = (s << len[i]) | ((1 << (len[i] - 1)) - 1);
	return s;
}

void dfs(int rem, int st)
{
	if (rem == 0) {
		LL cur = 0;
		for (int i = 0; i < (1 << n); ++ i)
			if ((popcount(i) ^ n) & 1) cur -= tmp[tot][i];
			else cur += tmp[tot][i];
		// for (int i = 1; i <= tot; ++ i) std::cout << len[i] << ' ';
		// std::cout << ": " << cur << '\n';
		do ans[getsta()] = cur; while (std::next_permutation(len + 1, len + tot + 1));
		return;
	}
	if (rem < st) return;
	++ tot;
	for (int i = st; i <= rem; ++ i) {
		len[tot] = i;
		for (int s = 0; s < (1 << n); ++ s)
			tmp[tot][s] = tmp[tot - 1][s] * f[i][s];
		dfs(rem - i, i);
	}
	tot --;
}

int main()
{
	std::cin >> n;
	for (int i = 0; i < n; ++ i) {
		static char s[N];
		scanf("%s", s);
		for (int j = 0; j < n; ++ j) a[i][j] = s[j] & 1;
	}
	for (int i = 0; i < n; ++ i) dp[1 << i][i] = 1;
	for (int s = 1; s < (1 << n); ++ s)
		for (int i = 0; i < n; ++ i) if (dp[s][i])
			for (int nxt = 0; nxt < n; ++ nxt)
				if (a[i][nxt] && (~s >> nxt & 1))
					dp[s | (1 << nxt)][nxt] += dp[s][i];
	for (int s = 0; s < (1 << n); ++ s)
		for (int i = 0; i < n; ++ i) f[popcount(s)][s] += dp[s][i];
	f[0][0] ++;
	// for (int i = 0; i <= n; ++ i, std::cout << '\n')
		// for (int s = 0; s < (1 << n); ++ s) std::cout << f[i][s] << ' ';
	for (int i = 0; i <= n; ++ i)
		for (int bit = 0; bit < n; ++ bit)
			for (int j = 0; j < (1 << n); ++ j)
				if (j >> bit & 1) f[i][j] += f[i][j ^ (1 << bit)];
	for (int s = 0; s < (1 << n); ++ s) tmp[0][s] = 1;
	dfs(n, 1);
	for (int bit = 0; bit < n - 1; ++ bit)
		for (int j = 0; j < (1 << (n - 1)); ++ j)
			if (j >> bit & 1) ans[j ^ (1 << bit)] -= ans[j];
	for (int s = 0; s < (1 << (n - 1)); ++ s) std::cout << ans[s] << ' ';
	std::cout << '\n';
	return 0;
}