题解：P11391 [COCI 2024/2025 #1] 疑惑 / Zbunjenost

· · 题解

Fastest solution :D

我们考察一个环的形态。以环上编号最小的点为起点，我们考虑如果说某一次用了三角剖分上的一条边向后跳，那么不可能再跳回来，因为这些边两两互不相交。

所以最后的路径应该形如走一段外面的环，跳一步，重复若干次直到最后跳一步回到起点。这里我们的点的编号一定是单调递增的。（当然这里把 n\to 1 也视为一条额外边）

那么我们可以枚举最后一步走的是哪条边，也就是要计算在链上从 s 走到 t 的方案数。乍一看有些不可做，但是实际上发现我们本质上在计算有多少种选出额外边的方式，使得他们可以串成一条路径，也就是说他们互不相交。

由于是三角剖分，额外边一定是两两包含或相离，所以可以建成一棵树的结构。问题变成在这棵树上选出一些点使得不存在任何有祖先后代关系的点同时被选择。

可以轻松写出一个 dp：设 f_u 为子树 u 中合法非空点集的个数，那么 f_u = 1+\prod(f_v+1)，其中 v 是 u 的儿子。那么我们实际上算的就是所有 f_u 之和，因为每条额外边都要累加一次。

直接用单调栈扫一遍 dp 就 ok 了，不需要把树建出来。用桶排可以做到 \mathcal O(n)。

const ll N = 2e5 + 9, Mod = 1e9 + 7;
ll n, stk[N], top, dp[N], ans;
array<ll, 2> a[N];
Ve<pii> vec[N];
bool Med;
int main() {
    cerr << fabs(&Med - &Mbe) / 1048576.0 << "MB\n";
    n = read();
    rep(i, 1, n - 3) {
        a[i][0] = read(), a[i][1] = read();
        if(a[i][0] > a[i][1]) swap(a[i][0], a[i][1]);
        vec[a[i][0]].pb({a[i][1], i});
    }
    a[n - 2] = {1, n};
    sort(a + 1, a + n - 1, [&](array<ll, 2> a, array<ll, 2> b) {
        return a[0] > b[0] || (a[0] == b[0] && a[1] < b[1]);
    });
    rep(i, 1, n - 2) {
        dp[i] = 1;
        while(top && a[stk[top]][1] <= a[i][1]) dp[i] = dp[i] * (dp[stk[top]] + 1) % Mod, --top;
        stk[++top] = i, ans += dp[i];
    }
    write(ans % Mod), putchar('\n');
    cerr << "\n" << clock() * 1.0 / CLOCKS_PER_SEC * 1000 << "ms\n";
    return 0;
}