【题目描述】
将(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)
代码
#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
", dp[n][k]);
return 0;
}