1 条题解
-
1
CF1580B Mathematics Curriculum
题目大意
在一个排列中我们定义 是好的当且仅当排列中所有包含 的子串中恰好有 种不同的子串内元素最大值。询问恰好有 个好元素的 排列数量。
分析
不难发现排列中包含 的子串的不同的子串内最大值数量等于 向左的最长上升子序列长度加上向右的最长上升子序列长度,而这个值是等于对原序列建立笛卡尔树后 到树根之间的距离。询问转化为询问有多少个 排列满足其笛卡尔树上恰好有 个结点深度为 。
考虑笛卡尔树的建立过程,我们每次从整个序列中取出最大值,然后从这个最大值所在的位置将原序列分为两半递归构造。我们可以考虑进行区间 DP, 表示 到 之间的满足笛卡尔树上恰好有 个点深度为 的排列数量。转移时我们枚举一个 ,钦定他为区间内的最大值,然后将区间分为两半,再暴力枚举这 个深度为 的点中有几个是在左区间,最终使用组合数将左右区间的两个排列合并起来即可。进一步我们发现 和 的具体值我们并不关心,因此仅记录区间长度即可。
时间复杂度 ,空间复杂度 。需要加上一些剪枝。
代码
Code
/** * @author Macesuted (i@macesuted.moe) * @copyright Copyright (c) 2021 */ #include <bits/stdc++.h> using namespace std; #define int long long #define maxn 105 typedef pair<int, int> pii; int f[maxn][maxn][maxn]; int C[maxn][maxn], fac[maxn]; int n, m, k, mod; int dp(int len, int up, int cnt) { if (!len) return cnt == 0; if (up == 1) return cnt == 1 ? fac[len] : 0; if ((cnt - 1) * 2 > len) return 0; if (f[len][up][cnt] >= 0) return f[len][up][cnt]; int answer = 0; for (int mid = 0; mid < len; mid++) for (int t = 0; t <= cnt; t++) answer = (answer + dp(mid, up - 1, t) * dp(len - mid - 1, up - 1, cnt - t) % mod * C[len - 1][mid]) % mod; return f[len][up][cnt] = answer; } void work(void) { memset(f, -1, sizeof(f)); cin >> n >> m >> k >> mod; fac[0] = 1; for (int i = 1; i < maxn; i++) fac[i] = fac[i - 1] * i % mod; for (int i = 0; i < maxn; i++) { C[i][0] = C[i][i] = 1; for (int j = 1; j < i; j++) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod; } cout << dp(n, m, k) << endl; return; } signed main() { ios::sync_with_stdio(false); cout << setiosflags(ios::fixed) << setprecision(11); int _ = 1; // cin >> _; while (_--) work(); return 0; }
- 1
信息
- ID
- 7327
- 时间
- 2000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 2
- 已通过
- 2
- 上传者