小兔的话

推荐

小兔的CSDN

序列的计算

题目限制

• 内存限制：128MiB
• 时间限制：1000ms
• 标准输入输出

题目知识点

• 思维
• 递推
• 动态规划 \(dp\)

为了方便大家阅读通畅，题目可能略有改动，保证不会造成影响

题目

题目背景

有一个集合 \(\{ 1, 2, 3, ..., n \}\)

将集合里面的所有元素构成若干个序列 \(\{ a_1, a_2, a_3 ··· a_n \}\)，并且定义 \(E\) 值为序列中 \(a_i > i\) 的元素个数

例如：

序列 \(1, 3, 2, 4\) 的 \(E\) 值为 \(1\)；其中 \(a_2 = 3 > 2\)

序列 \(4, 3, 2, 1\) 的 \(E\) 值为 \(2\)；其中 \(a_1 = 4 > 1, a_2 = 3 > 2\)

题目描述

现在给你 \(n\) 和 \(k\)，请你找出由集合 \(\{ 1, 2, 3, ··· n \}\) 构成的所有序列当中，有多少个序列的 \(E\) 值为 \(k\)

格式

本题是无限输入

输入格式

对于每组输入的数据：

输入共 \(1\) 行，包含 \(2\) 个整数 \(n\) 和 \(k\)

输出格式

对于每组输入的数据：

输出共 \(1\) 行，包含 \(1\) 个整数，表示答案

有可能答案会非常的大，请输出答案 \(\mathrm{mod}\) \((1e9 + 7)\) 的值。

样例

样例输入

3 0
3 1
           

样例输出

1
4
           

提示

数据范围

对于 \(100\%\) 的数据：

\(1 \leq n \leq 1000\)

\(0 \leq k \leq n\)

思路

这题首先想到的是搜索，但 数据范围不适合 和 无限输入 表明了不可能是搜索

除了搜索，就只能想到递推了

定义 \(dp[i][j]\) 表示：用 集合 \(\{ 1, 2, 3 ··· i \}\) 能构成 \(E\) 值为 \(k\) 的序列个数

记 用集合 \(\{ 1, 2, 3 ··· i \}\) 构成的序列为 \(a\)

可以发现，\(a\) 所构成的任意一种序列 \(\{ a_1, a_2, a_3 ··· a_i \}\) 都可以通过 \(\{ a_1, a_2, a_3 ··· a_{i-1}, a_i = i \}\) 把 \(a_i\) 与 之前的 \(i - 1\) 个数之一 交换得到

对于一种状态 \(dp[i][j]\)，由于 \(a_i\) 只能贡献 \(0\) 或 \(1\)，所以有 \(2\) 种情况：

• 若 集合 \(\{ 1, 2, 3 ··· i-1 \}\) 构成 \(E\) 值为 \(j\)，故 \(a_i\) 是不做贡献的；当前 集合是 \(\{ a_1, a_2, a_3 ··· a_i = i \}\)，\(a_i\) 只能 不交换 或者 与前面已经做了贡献的位置交换，故有 \(j + 1\) 种情况；即 \(dp[i - 1][j] * (j + 1)\)
• 若 集合 \(\{ 1, 2, 3 ··· i-1 \}\) 构成 \(E\) 值为 \(j - 1\)，故 \(a_i\) 是做贡献的；当前 集合是 \(\{ a_1, a_2, a_3 ··· a_i = i \}\)，\(a_i\) 只能 与前面已经没做贡献的位置交换，故有 \((i - 1) - (j - 1) = i - j\) 种情况；即 \(dp[i - 1][j - 1] * (i - j)\)

综上所述：\(dp[i][j] = dp[i - 1][j] * (j + 1) + dp[i - 1][j - 1] * (i - j)\)；但是当 \(j = 0\) 的时候，序列 \(a\) 只有 \(\{ 1, 2, 3 ··· i \}\) 一种方案

分析

由于 \(a\) 这个序列只包含元素 \(\{ 1, 2, 3, ..., i \}\)，与其它数无关；\(dp[i][j]\) 也只与 \(i, j\) 有关

我们可以先预处理出 \(dp\)，输入 \(n\) 和 \(k\) 之后直接输出 \(dp[n][k]\) 即可

for (int i = 1; i <= MAXN; i++)
{
	for (int j = 0; j < i; j++) // E值 不可能超过 i, 而且不可能有 j >= i 的序列 
	{
		if (j == 0) { dp[i][j] = 1LL; continue; }
		dp[i][j] = (dp[i][j] + dp[i - 1][j] * (j + 1)) % MOD;
		dp[i][j] = (dp[i][j] + dp[i - 1][j - 1] * (i - j) % MOD) % MOD;
	}
}
           

代码

#include <cstdio>

#define i32 int
#define i64 long long
#define u32 unsigned i32
#define u64 unsigned i64

const int MOD = 1e9 + 7;
const int MAXN = 1e3, MAXK = MAXN;
int N, K;
i64 dp[MAXN + 5][MAXK + 5];

int main()
{
	for (int i = 1; i <= MAXN; i++)
	{
		for (int j = 0; j < i; j++)
		{
			if (j == 0) { dp[i][j] = 1LL; continue; }
			dp[i][j] = (dp[i][j] + dp[i - 1][j] * (j + 1)) % MOD;
			dp[i][j] = (dp[i][j] + dp[i - 1][j - 1] * (i - j) % MOD) % MOD;
		}
	}
	while (scanf("%d %d", &N, &K) != EOF)
		printf("%lld\n", dp[N][K]);
	return 0;
}