[AGC024E] Sequence Growing Hard 题解

题目链接：[AGC024E] Sequence Growing Hard

题意：

给定 \(n,m,P\) ，问有多少个序列组 \((A_0,A_1,\cdots,A_n)\) 满足：

• 序列 \(A_i\) 的元素个数为 \(i\) ；
• 所有元素都在 \([1,m]\) 内；
• \(\forall i\in[0,n)\) ，\(A_i\) 是 \(A_{i+1}\) 的子序列且 \(A_i\) 的字典序小于 \(A_{i+1}\) 。

输出在\(\bmod P\) 意义下的答案.

数据范围：

\(1\le n, m \le 300,~2\le P \le 10^9\) 。

正着考虑看上去很麻烦，不妨反着来看这个序列组。

显然这个序列组就是从 \(A_n\) 删除某个元素得到 \(A_{n-1}\) ，再删除一个得到 \(A_{n-2}\) ，以此类推。

那么根据字典序的性质，如果我们删除 \(i\) 位置的元素，得到一个字典序更小的，

就要求 \(i\) 后面第一个不等于它的元素比它小，因为 \(a_{i+1}\) 可能和 \(a_i\) 一样大，这题没说是排列。

这个就很麻烦了，不过我们可以钦定颜色相同的段就删最后一个，这样就只需要比较 \(a_i\) 和 \(a_{i+1}\) 的大小了。

设 \(f(i,j)\) 表示长度为 \(i\) 的序列只用了 \([1,j]\) 的元素的方案数。

转移的话，为了防止重复，我们枚举第一个 \(j\) 出现的位置 \(k\) ，和它被删除的时刻 \(p\) ，

那么 \(k\) 后面的 \(i-k\) 个数就需要在前 \(p-1\) 个时刻内被删除，那么 \[ f(i,j) =\sum_{k=1}^{i}\sum_{p = i - k + 1}^i\binom{p-1}{i-k} f(k - 1,j-1)f(i-k,j) \] 这个 \(\sum_{p = i - k + 1}^i\binom{p-1}{i-k}\) 可以记作 \(g(i,k)\) 并预处理出来，即 \[ f(i,j) = \sum_{k=1}^{i}g(i,k)f(k - 1,j-1)f(i-k,j) \] 有一说一，这个 \(k\) 和 \(p\) 的设计确实很巧妙，感觉我就卡在这一步。

时间复杂度 \(\mathcal{O}(n^3)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(333))

int n, m, mod, C[N][N], f[N][N], g[N][N];
void add(int &x, int y) { (x += y) >= mod ? x -= mod : 0; }
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m >> mod;
    rep(i, 0, n) C[i][0] = C[i][i] = 1;
    rep(i, 0, n) rep(j, 1, i - 1) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
    rep(i, 1, n) rep(k, 1, i) rep(p, i - k + 1, i) add(g[i][k], C[p - 1][i - k]);
    rep(j, 0, m) f[0][j] = 1;
    rep(j, 1, m) rep(i, 1, n) {
        rep(k, 1, i) add(f[i][j], f[k - 1][j - 1] * f[i - k][j] % mod * g[i][k] % mod);
        add(f[i][j], f[i][j - 1]);
    }
    cout << f[n][m] << '\n';
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/article/12swqlqs

---

题外话：

我就放图片。