数学 Trick 之：宽限+反演

能够解决的问题

有不好刻画/转移的勾石限制的一些问题。

优缺点

优点：代码简单，且这一类基本上都是区分度高的题。

缺点：适用性不广泛。

思路

既然有勾石限制，那我们就宽限！

我们可以尝试将限制变简单，然后就可以考虑能否反演。

注：此时一定不要想着这个新限制能否转移，否则大脑容易焦虑，退缩，只管推反演就行了。

当我们发现一个能反演的更简单的性质了，我们可以考虑转移，然后：

如果 TLE，就再放宽。
实在放不宽，果断放弃。

思路比较抽象，我们通过一个具体例题来讲。

例题与代码

P3349 [ZJOI2016] 小星星

这道题中恶心的限制在于：

必须与原图一一对应（不重不漏用每个点）。

那么我们就可以考虑放宽一点，既然单射太难，那么就多射，变为：

原图每个点都唯一对应树上的点集 $S$ 。

此时，我们可以列出状态

dp_{u,S}

表示

u

的子树中，可以重复的用点集

S

的点对应。

我们发现这样不好转移，因为我们无法得知图中转移边（即父亲与儿子对应点间的边）的有无，所以我们加一维：

dp_{u, j, S}

表示

u

的子树中，

u

对应

j

，可以重复的用点集

S

的点对应。

那么我们有（不要问我怎么推出来的，都这个程度了）：

dp_{u, j, S} = \sum_{son \in\text{E}(u) \setminus fa_u}\sum_{k \in S}dp_{son, k, S}[(j, k) \in \text{G}]

时间复杂度

O(n^32^n)

，这题需要卡常，

60\text{pts}

就够了。

CPP

#include <bits/stdc++.h>
using namespace std;

#define int long long
constexpr int maxn = 18, maxk = 131072;

int n, m, a, b, dp[maxn][maxn][maxk], G[maxn][maxn], g[maxk], f[maxk], ans, K, sz[maxk];
vector <int> T[maxn];

int kth(int S, int k) {
	return ((S >> (k - 1)) & 1);
}
int siz(int S) {
	int ress = 0;
	for (int i = 1; i <= n; i++) {
		ress += kth(S, i);
	}
	return ress;
}

void dfs(int t, int g, int fa, int S) {
	if (dp[t][g][S]) return ;
	dp[t][g][S] = 1;
	int nowsum;
	for (int now : T[t]) {
		if (now == fa) continue;
		nowsum = 0;
		for (int i = 1; i <= n; i++) {
			if (kth(S, i) && G[g][i]) {
				dfs(now, i, t, S);
				nowsum += dp[now][i][S];
			}
		}
		dp[t][g][S] *= nowsum;
	}
	return ;
}

int p(int x) {
	return ((x & 1) ? -1 : 1);
}

signed main() {
	input.read(n, m);
	K = (1 << n);
	for (int S = 0; S < K; S++) {
		sz[S] = siz(S);	
	}
	for (int i = 1; i <= m; i++) {
		input.read(a, b);
		G[a][b] = G[b][a] = 1;
	}
	for (int i = 1; i < n; i++) {
		input.read(a, b);
		T[a].push_back(b);
		T[b].push_back(a);
	}
	for (int j = 1; j <= n; j++) {
		for (int S = 0; S < K; S++) {
			if (!kth(S, j)) continue;
			dfs(1, j, 0, S);
		}
	}
	
	for (int S = 0; S < K; S++) {
		for (int i = 1; i <= n; i++) {
			if (!kth(S, i)) continue;
			g[S] += dp[1][i][S];
		}
	}
	
	for (int S = 0; S < K; S++) {
		ans += p(n - sz[S]) * g[S];
	}
	
	output.write(ans, '\n');
	
	return 0;
}

数学 Trick 之：宽限+反演

文章操作

能够解决的问题

优缺点

思路

例题与代码

相关推荐

评论

数学 Trick 之：宽限+反演