【FJ2014集训】愚蠢的算法

2014年7月20日1,1250

问题描述

对于一个1~n的排列{p1,p2,…,pn},将pipj交换,需要的代价为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)

输入格式

输入nm,表示1~n的排列,以及确定了前m个数。

接下来一行包含m个数,表示排列中确定的前m个数。

输出格式

输出一行,表示有多少个排列满足条件,输出答案mod 10^9+7

样例输入1

3 0

样例输出 1

5

样例输入 2

5 2 1 4

样例输出 2

3

数据规模

对于20%的数据,n10

对于50%的数据,n200

对于100%的数据,n2000mn

题解

惊奇的发现,m=0的时候答案序列是卡特兰数列

于是就掉坑里了。。。

先贴个20分暴力。。。