落谷 P2401 不等数列

2024-10-18 18:54:13

题目链接。

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 <iostream>

#include <cstdio>

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]);

}

最新文章

热门文章