自动搬运

查看原文

来自洛谷，原作者为

	7KByte **

搬运于2025-08-24 22:36:45，当前版本为作者最后更新于2022-04-09 10:50:24，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

有个很奇妙的 $\mathcal{O}(n^22^n)$ 的做法。

首先题目等价于将给定图划分成若干个简单环，所以我们可以设计 DP 状态，$f_{x,S}$ 表示以 $x$ 结尾，经过节点为 $S$，以 $S$ 中最小的点出发的路径方案，如果 $x$ 到最小点有边，就更新 $h_{S}$ 表示点集为 $S$ 的环的方案。

然后我们再合并环，$g_{S}$ 表示将集合 $S$ 划分成若干环的方案，然后枚举最小点所在的环 $T$，有转移 $g_{S} = \sum \limits_{T\subseteq S} h_{T}g_{S/T}$，这样就可以做到 $\mathcal{O}(n^22^n + 3^n)$。

我一度认为 $3^n$ 是信息极限了，但是这题还有一些特殊性质。

我们观察到由 $h$ 可以直接推出 $g$，那么我们是否可以跳过 $h$ 这一步，直接由 $f\to g$。

那么我们更新一下状态，$f_{x, S}$ 表示已经 fix 了若干个环，然后当前路径是从 $S$ 中最小的点出发到 $x$ 结束的方案数，这样 $f_{x,S}$ 可以直接转移到 $g_{S}$。

但是这样 $f$ 就需要考虑新开一个环的可能，所以我们再从 $g\to f$，枚举比 $g_{S}$ 中最小的点更小的点 $x$ 作为起点，然后 $g_{S} \to f_{x, S\cup\{x\}}$。为什么要更小的点，因为避免一个划分方案重复统计，以环的最小的点为关键字从大到小依次考虑。

这样时间复杂度是 $\mathcal{O}(n^22^n)$。代码和上面描述有点区别，是以环的最大点作为关键字从小到大考虑，本质相同。

#define N 18
int n, a[N][N], e[N][N], bt[1 << N]; char ch[N + 5]; LL f[N][1 << N], g[1 << N];

int main() {
	read(n);
	rep(i, 0, n - 1){
		rep(j, 0, n - 1)read(a[i][j]), a[i][j] --;
		rep(j, 0, n - 1){
			e[i][a[i][j]] = 1;
			if(a[i][j] == i)break;
		}
	}
	int w = (1 << n) - 1;
	bt[0] = ~0; rp(i, w)bt[i] = bt[i >> 1] + 1;
	g[0] = 1;
	rep(s, 0, w){
		int k = bt[s];
		rep(i, 0, k){
			if(e[i][k])g[s] += f[i][s];
			rep(j, 0, k)if(!((s >> j) & 1) && e[i][j])
				f[j][s | (1 << j)] += f[i][s];
		}
		rep(i, k + 1, n - 1)f[i][s | (1 << i)] += g[s];
	}
	int T; read(T);
	while(T--){
		scanf("%s", ch);
		int s = 0;
		rep(i, 0, n - 1)if(ch[i] == 'H')s |= 1 << i;
		printf("%lld\n", g[s] * g[w ^ s]);
	}
	return 0;
}