题解：CF1874F Jellyfish and OEIS

jijidawang · 2025-06-22 15:25:43 · 题解

考虑一种类似析合树的结构，称一个段 [l,r] 是连续段当且仅当 p_{l\dots r} 是 l\dots r 的一个排列。一个连续段是本原段当且仅当不存在另一个连续段与其部分相交。

那么本原段要么包含要么不交，则包含关系可以形成一棵树的结构。称一个点是合点当且仅当任取它的连续的若干个儿子总能组成新的连续段，一个点是析点当且仅当任取它的连续的若干个儿子总不能组成新的连续段。本题中叶子不一定是连续段，但是为了方便将叶子也加入树中。对于一个叶子 [i,i] 来说，如果 a_i=i 则它是析点、否则它被称为非法叶子（虽然它被叫做非法叶子但是它还是叶子）。

反证法可证每个非叶子结点不是析点就是合点。接下来考虑析点和合点的子树结构。

对于合点来说，它的儿子必须是析点。否则一个合儿子 v 可以与它附近的兄弟组成连续段，这与 v 是本原段矛盾。
对于析点来说，它的儿子可以是析点、合点或非法叶子。但是任意两个析 / 合点间至少有一个非法叶子，否则它们可以拼起来形成新连续段。同时头尾也必须是非法叶子，否则除了头 / 尾的部分拼起来可以组成一个连续段。

那么接下来只需要对析合树结构 DP 就可以了，只需 f_{l,r,s} 表示合点 [l,r] 有 s 个儿子的方案数、g_{l,r,s} 表示合点 [l,r] 有 s 个非法叶子儿子的方案数，转移只需类似区间 DP 进行即可。

此处转移的困难性在于合并析点时需要计算非法叶子的方案数，容易发现问题相当于计算长度为 n 的只有 [1,n] 是连续段的排列个数 a_n。这是 Stabilized Interval Free (SIF) 排列计数问题。考虑递推，依次插入 1\dots n，令 1\dots n-1 部分最长的连续段长度为 s，分类讨论：

综上可得 a 的递推式：

a_n=(n-1)a_{n-1}+\sum_{s=1}^{n-3}(n-s-2)a_{n-s-1}a_{s+1}=(n-1)a_{n-1}+\sum_{j=2}^{n-2}(j-1)a_ja_{n-j}

其中 a_0=a_1=1。从而可以简单 \Theta(n^2) 递推得到 a 序列。

从而问题被完整解决，总时间复杂度 \Theta(n^4)，常数较小所以可以通过。

const int N = 205, M = N * N, P = 1000000007;
int n, m[N], inv[M], f[N][N][N], g[N][N][N], F[N][N], G[N][N], a[M];
inline void init(int n)
{
    a[0] = a[1] = inv[0] = inv[1] = 1;
    for (int i=2; i<=n; i++)
    {
        a[i] = 1ll * (i - 1) * a[i - 1] % P;
        for (int j=2; j<=i-2; j++) (a[i] += 1ll * (j - 1) * a[j] % P * a[i - j] % P) %= P;
    }
    for (int i=2; i<=n; i++) inv[i] = 1ll * (P - P / i) * inv[P % i] % P;
}
int main()
{
    scanf("%d", &n); init(n * (n + 1) / 2);
    for (int i=1; i<=n; i++) scanf("%d", m+i);
    for (int i=1; i<=n; i++)
    {
        f[i][i - 1][0] = g[i][i][1] = 1;
        if (i > m[i]) f[i][i][1] = G[i][i] = 1;
    }
    for (int l=n; l>=1; l--)
        for (int r=l+1; r<=n; r++)
        {
            int len = r - l + 1;
            for (int i=l+1; i<r; i++)
                for (int c=1; c<=len; c++) (g[l][r][c] += 1ll * g[l][i - 1][c - 1] * (F[i][r - 1] + G[i][r - 1]) % P) %= P;
            for (int c=1; c<=len; c++) (g[l][r][c] += g[l][r - 1][c - 1]) %= P;
            if (r > m[l])
            {
                for (int c=2; c<=len; c++) (G[l][r] += 1ll * g[l][r][c] * a[c] % P) %= P;
                for (int i=l; i<=r; i++)
                    for (int c=1; c<=len; c++) (f[l][r][c] += 1ll * f[l][i - 1][c - 1] * G[i][r] % P) %= P;
                for (int c=2; c<=len; c++) (F[l][r] += f[l][r][c]) %= P;
            }
        }
    printf("%d\n", (F[1][n] + G[1][n]) % P);
    return 0;
}