题解 P7024 【[NWRRC2017]Fygon 2.0】
Starlight237
·
·
题解
首先介绍如何对 DAG 求拓扑序的个数。
下面回到本题：
> (**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 求出。
```cpp
#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;
}
```