#BZOJ3692. 愚蠢的算法
-
ID: 2243
Type: RemoteJudge
1000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
root
愚蠢的算法
No submission language available for this problem.
题目描述
对于一个1~n的排列{p1,p2,…,pn}，将pi和pj交换，需要的代价为2*|i-j|-1，记f(p)表示通过交换将排列p变成从小到大的排列，即{1,2,3…,n}的最小代价。一个愚蠢的算法是用g(p)=Σmax(0, i-pi)来估算f(p)。给出1~n的排列的前m个元素，求有多少个排列p满足条件f(p)=g(p)。
输入格式
输入n和m，表示1~n的排列，以及确定了前m个数。
接下来一行包含m个数，表示排列中确定的前m个数。
输出格式
输出一行，表示有多少个排列满足条件，输出答案mod 10^9+7。
样例输入1
3 0
样例输入 2
5 2 1 4
样例输出 1
5
样例输出 2
3
数据范围与约定
对于100%的数据，n≤2000，m≤n