【题目描述】
将$1$到$n$任意排列,然后在排列的每两个数之间根据他们的大小关系插入“$>$”和“$<$”。问在所有排列中,有多少个排列恰好有$k$个“$<$”。答案对$2012$取模。

【输入格式】
第一行$2$个整数$n,k$。

【输出格式】
一个整数表示答案。

【数据范围】
对于30%的数据:$n \leq 10$
对于100%的数据:$k < n \leq 1000$

题解
考虑一个比较简单的情况$2, 1, 3$
这个序列现在有$1$个$<$和$1$个$>$
假设现在要把$4$插入这个序列
(1) 如果要将$4$放到原有的两个数之间 因为$4$一定会是当前序列中最大的 所以会新产生一个$<$和一个$>$。如果插入的位置原来是$>$则$<$的总量会+1 反之$>$的总量会+1
(2) 如果把$4$放在最左边 就会新产生一个$>$如果放在最右边就会新产生一个$<$

综上$4$一共有四个位置可以插入 其中有两个位置会使$<$的总数+1 另外两个位置会使$>$的总数+1
对于一般情况 如果当前要插入$i$则一共会有正好$i$个位置可供插入 设目前有$j$个$<$则会有$i-j-1$种情况使得$<$增多一个 会有$j+1$种情况使得$>$增多一个
然后就可以DP了 设$f[i][j]$表示$1$~$i$的排列中有$j$个$<$的方案数 则转移方程为$f[i][j]=f[i-1][j-1]*(i-j)+f[i-1][j]*(j+1)$
边界:$f[2][0]=f[2][1]=1$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;

const ll mod = 2012;
ll n, k;
ll dp[1005][1005];

int main() {
scanf("%lld %lld", &n, &k);
dp[2][0] = dp[2][1] = 1;
for (ll i = 3; i <= n; i++) {
for (ll j = 0; j <= min(k, i - 1); j++) {
dp[i][j] = (dp[i][j] + dp[i-1][j-1] * (i - j)) % mod;
dp[i][j] = (dp[i][j] + dp[i-1][j] * (j + 1)) % mod;
}
}
printf("%lld\n", dp[n][k]);
return 0;
}

评论