自动搬运

查看原文

来自洛谷，原作者为

	Starlight237 [Drawer/auth]EgcqEzGZV+k435xMKiYIpABsjWY0ln/huv6DW7QW9Qw=

搬运于2025-08-24 22:25:58，当前版本为作者最后更新于2021-11-01 15:26:05，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

首先介绍如何对 DAG 求拓扑序的个数。

$f_S$ 表示点集 $S$ 中拓扑序的个数，枚举拓扑序中最后面的点 $v$，则当 $v\in S$ 且 $v$ 不存在通往 $S$ 的出边时，容易建立从 $S-\{v\}$ 的拓扑序到 $S$ 的拓扑序的单射（直接把 $v$ 加到最后）。因而可以将 $f_S$ 加上 $f_{S-\{v\}}$。很显然，这覆盖了所有可能的情况。

下面回到本题：

(2021集训队作业 P7024 【[NWRRC2017]Fygon 2.0】)给定 $m$ 层嵌套的 for 循环语句，每个循环包含循环变量和上下界，其中上下界是外层变量或 $1$ 和 $n$，求关于 $n$ 的渐进复杂度和最高次项系数（常数）。最内层是一个语句 lag，其复杂度被认为是 $O(1)$。

对所有涉及到的变量和上下界都建立结点（整数变量） $\{u_k\}$，将一个 for ui in range(uj,uk) 的循环视为两个整数不等式 $u_j\le u_i\le u_k$。则 lag 的执行次数就等于该不等式组的正整数解数。

考虑建立图论模型，若 for 循环中有 $u_i\le u_j$ 的约束（若其中有 $1$ 或 $n$，视为没有约束），则建边 $u_i\rightarrow u_j$。对该图进行缩点，形成一个由 SCC（强连通分量） 组成的 DAG。易见每个 SCC 中所有点的取值都是相同的，不妨设为 $v_1,v_2,...,v_k$（一共有 k 个 SCC）。我们只要求出了该 DAG 的一个拓扑序，则从小到大随意给 $v_1,...,v_k$ 赋值为 $[1..n]$ 中的互不相同的整数，便得到了该拓扑序对应的 $\binom nk$ 组解，于是总执行次数就是 $N\binom nk$，其中 $N$ 是拓扑序个数。从而渐进复杂度就是 $O(n^k)$。常数项为 $\lim_{n\rightarrow\infty}N\binom nk/n^k=N/k!$。

这里 $N$ 就可以用上述的方法，状压 DP 求出。

#define ctz __builtin_ctz
const int S = 1048586;
int m, tab[128], tot;
ll f[S];
inline int newnode(int x) {
	return (x == '0' || x == 'n' ? 0 : tab[x] ? tab[x] : tab[x] = ++tot) - 1;
}
int eg[21], eg_[S], dfn[21], low[21], tim, ins, cnt = -1, rt[21];
stack<int>stk;
void tarjan(int x) {
	dfn[x] = low[x] = ++tim, stk.push(x), ins |= 1 << x;
	for (int v, i = eg[x]; i; i &= i - 1)
		if (!dfn[v = ctz(i)]) tarjan(v), low[x] = min(low[x], low[v]);
		else if (ins >> v & 1) low[x] = min(low[x], dfn[v]);
	if (dfn[x] == low[x]) {
		++cnt; int y;
		do y = stk.top(), rt[y] = cnt, ins &= ~(1 << y), stk.pop(); while (y != x);
	}
}
int main() {
	freopen("1.in", "r", stdin);
	m = rd();
	for (int i = 1; i <= m; ++i) {
		char ch = gtc();
		while (ch != 'f' && ch != 'l') ch = gtc();
		if (ch == 'f') {
			gtc(); gtc(); int x = gtc();
			gtc(); gtc(); gtc(); gtc(); gtc(); gtc(); gtc(); gtc();
			int l = gtc(); gtc(); int r = gtc();
			x = newnode(x), l = newnode(l), r = newnode(r);
			if (~l) eg[l] |= 1 << x;
			if (~r) eg[x] |= 1 << r;
		}
	}
	for (int i = 0; i < tot; ++i)
		if (!dfn[i]) tarjan(i);
	for (int i = 0; i < tot; ++i)
		for (int j = eg[i], v; j; j &= j - 1)
			if (rt[i] != rt[v = ctz(j)])
				eg_[rt[i]] |= 1 << rt[v];
	ll fac = 1;
	for (int i = 2; i <= cnt; ++i) fac *= i;
	f[0] = 1;
	for (int i = 1, all = ~(-1 << cnt); i <= all; ++i)
		for (int j = i, v; j; j &= j - 1)
			if (!(eg_[v = ctz(j)] & i)) f[i] += f[i & ~(1 << v)];
	ll fs = f[~(-1 << cnt)], g = __gcd(fs, fac);
	printf("%d %lld/%lld", cnt, fs / g, fac / g);
	return 0;
}