落谷 P2401 不等数列

题目链接。

Solution

状态设计

设 \(f_{i, j}\) 为 \(1\) 到 \(i\) 的排列，其中有 \(j\) 个 \(\text{‘<’}\) 的方案数。

状态转移

尝试从 \(i\) 转移到 \(i + 1\)，实质是考虑把 \(i + 1\) 插入到序列的哪个位置。

• 如果插入到最左边，会新增一个大于号(\(1\) 种情况)
• 如果插入到最右侧，会新增一个小于号(\(1\) 种情况)
• 如果插入到一个小于号之间，会破坏一个小于号，产生一个小于号和一个大于号，相当于新增一个大于号(\(j\) 种情况)
• 如果插入到一个大于号之间，会破坏一个大于号，产生一个大于号和一个小于号，相当于新增一个小于号(\(i - 1 - j\) 种情况)

综上所述：

• 有 \(j + 1\) 种情况增加一个大于号，即 \(f[i + 1][j] \gets f[i][j] * (j + 1)\)
• 有 \(i - j\) 种情况增加一个小于号，即 \(f[i + 1][j + 1] \gets f[i][j] * (i - j)\)

Code

#include 
#include using namespace std;const int N = 1005, P = 2015;int n, K, f[N][N];int main() {scanf("%d%d", &n, &K);f[1][0] = 1;for (int i = 1; i < n; i++) {for (int j = 0; j < i; j++) {(f[i + 1][j] += f[i][j] * (j + 1)) %= P;(f[i + 1][j + 1] += f[i][j] * (i - j)) %= P;}}printf("%d\n", f[n][K]);
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！