落谷 P2401 不等数列

题目链接。

Solution

状态设计

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

状态转移

尝试从 (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
", f[n][K]);
}