AHSOFNU NOIP模拟题-1 T2(DP+乘法原理)

对于$1-n$等类似的排列计数问题,以动态规划和组合数学2种大方向为基本解决方向。
我们从小到大插入数字,因此我们现在插的这个数比现在所有在序列里的数都要大。
这样一来就不需要记录是哪些数字插入了(而只要记录插入到了第几个数字),同时不需要记录每个数字的具体位置,也不需要记录数字的相对位置,而只需记录相对关系的数目(对本题而言就是有几个“<”)
我们设$dp(i, j)$表示前$i$个数字构成的数列中,恰有$j$个”<”号的方案数(“>”号就有$i-j-1$个)
考虑插入数的位置:
1、插入在两个数关系为”<”之间:
显然这样插入会增加一个“>”,那么有$j+1$个位置可以插,那么有状态转移方程$dp(i, j) += dp(i-1, j) * (j+1)$
2、插入在两个数关系为”>”之间:
显然这样插入会增加一个“<”,那么有$(i-j+1)-1$个位置可以插,那么有状态转移方程$dp(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)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define FN2 "num"
using namespace std;
const int MAXN = 1000 + 5, MO = 2012;
int n, k, dp[MAXN][MAXN];
void clean() {
}
void solve() {
clean();
scanf("%d%d", &n, &k);
dp[1][0] = 1;
for (int i=2;i<=n;i++) {
dp[i][0] = 1;
for (int j=1;j<n;j++) {
dp[i][j] = (dp[i][j]%MO + (dp[i-1][j]*(j+1))%MO + (dp[i-1][j-1]*(i-j)%MO))%MO;
}
}
printf("%d\n", dp[n][k]%MO);
}
int main() {
freopen(FN2".in", "r", stdin);freopen(FN2".out", "w", stdout);
solve();
fclose(stdin), fclose(stdout);
return 0;
}

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

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

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

【样例输入】
5 2
【样例输出】
66
【数据范围】
对于30%的数据:n <= 10
对于100%的数据:k < n <= 1000,

------ 本文结束 ------