[题解] [AGC024E] Sequence Growing Hard

· · 题解

UPD 24/12/13 修正笔误：\binom{i+j-2}{j} 应为 \binom{i+j-2}{j - 1}。

即每次插入一个数，使得每次操作后序列的字典序大于操作前的数组。观察发现，一个数只有插入在小于它的数前面，或插入在序列尾，才一定能使字典序变大。可以在序列尾放一个无穷小的虚点，方便实现。

考虑怎样计数操作，不会做。试想更简单的问题：对于一个确定的序列，怎样刻画“插入”操作并对其计数？根据性质，一个数会插入在另一个数前。因此，可以考虑向位置靠后的数连边。这样，每个位置都有一个出边，只有虚点没有出边。所以这是一棵树，树上每个节点的父亲的权值都严格小于它。

这样，对于确定的序列，一个插入方案可以被写成一棵树，一棵确定的树也就可以对应一个插入方案。不交子树之间，贡献互不影响。于是转化为计树。

计树题就可以比较方便地做。设 f_k(i) 表示根节点填 k，树的大小为 i 的方案数。每次在最前面加入一棵子树以规避算重——这样加入的子树的根必须紧接着原树的根之后插入——值得注意的是，根据定义，这样加入子树即是“有序”的。可以得到：

f_k(i+j) \gets \binom{i+j-2}{j - 1}f_k(i)f_{k'>k}(j)

。其中组合数表示：钦点完根和加入子树的根，剩下的时刻选一些时刻放入操作。

于是就可以 DP. 进行后缀和优化之后复杂度为 O(n^2k)。

const int N = 305;
int n, m; ll P;
ll C[N][N];
ll f[N][N], s[N][N];

int main() {
    rd(n, m, P);
    U (i, 0, N - 1) {
        C[i][0] = 1;
        U (j, 1, i)
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % P;
    }

    U (k, 0, m) f[k][1] = 1;
    D (k, m, 0) s[k][1] = (s[k + 1][1] + f[k][1]) % P;
    // f_k(i+j) <- f_k(i)f_{k' > k}(j) * C_{i-2+j}^{j}
    // f_k(i) = \sum_{x+y=i, x,y>=1} f_k(x) * s_{k+1}(y) * C_{i-2}^y
    U (i, 2, n + 1) {
        U (k, 0, m)
            U (x, 1, i - 1)
                (f[k][i] += C[i - 2][x - 1] * f[k][x] % P * s[k + 1][i - x]) %= P;
        D (k, m, 0) (s[k][i] = s[k + 1][i] + f[k][i]) %= P;
    }
    printf("%lld", (f[0][n + 1] % P + P) % P);
}