序列的计算
小兔的话
推荐 小兔的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;
}