嘘~ 正在从服务器偷取页面 . . .

[AGC024E] Sequence Growing Hard 题解

发布日期: 2024-06-26

更新日期: 2024-06-26

文章字数: 742

[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;
}