将1到n任意排列，然后在排列的每两个数之间根据他们的大小关系插入“>”和“<”。问在所有排列中，有多少个排列恰好有k个“<”。答案对2015取模。
注：1~n的排列指的是1~n这n个数各出现且仅出现一次的数列。
第一行2个整数n,k。
一个整数表示答案。
5 2
66
对于30%的数据：n <= 10
对于100%的数据：k < n <= 1000
【解题思路】
dp[i][j]=dp[i-1][j-1]*(i-j)+dp[i-1][j]*(j+1);
其中i和j是表示前i个数中有j个小于号，j<=i-1
如何理解这个方程？？
要在长度为i的数列中插入一个数，那么共有i+1个位置可以插入（第一个位置最后一个位置和中间的i-1个位置）。由于插入的数字大于之前所有数，那么在原串中是小于号的位置插入这个数会多出来一个大于号，小于号数量则不变，如果在大于号位置插入会多一个小于号，而插在头位置也多一个大于，末位置多一个小于，总计，使小于号数量不变的位置有（j+1）个，剩下的（i-j）个位置会使小于号数量增加
【code】
1 #include <cstdio>
2 #include <iostream>
3 #include <algorithm>
4 using namespace std;
5 int n,k,f[1005][1005];
6 const int mod=2015;
7 int main(){
8 ///freopen("2401.in","r",stdin);
9 //freopen("2401.out","w",stdout);
10 scanf("%d%d",&n,&k);
11 for (register int i=1;i<=n;i++)
12 f[i][0]=1;
13 for (register int i=2;i<=n;i++)
14 for (register int j=1;j<=k;j++)
15 f[i][j]=(f[i-1][j-1]*(i-1-j+1)+f[i-1][j]*(j+1))%mod;
16 printf("%d\n",f[n][k]);
17 return 0;
18 }
原文：https://www.cnblogs.com/66dzb/p/11257394.html