AK-dream

【题目描述】
将$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;
}


 评论