#P6317. 「JOI Open 2016」摩天大楼

    ID: 5806 传统题 2000ms 512MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-线性 DP计数 DP贡献法滚动数组

「JOI Open 2016」摩天大楼

题目描述

译自 JOI Open 2016 T3 「高層ビル街 / Skyscraper」

将互不相同的 NN 个整数 A1,A2,…,ANA_1, A_2, \dots, A_N 按照一定顺序排列。
假设排列为 f1,f2,…,fNf_1, f_2, \dots, f_N,要求:$| f_1 − f_2| + | f_2 − f_3| + \dots + | f_{N−1} − f_N| ≤ L$。
求满足题意的排列的方案数  mod (109+7)\bmod (10^9+7)。

输入格式

第一行有两个整数 N,LN, L。
第二行有 NN 个整数 A1,A2,…,ANA_1, A_2, \dots, A_N。

输出格式

一行,一个整数,表示方案数  mod (109+7)\bmod (10^9+7)。

4 10
3 6 2 9
6
8 35
3 7 1 5 10 2 11 6
31384

数据范围与提示

对于所有数据,1≤N≤100,1\le N\le 100, 1≤L≤1000,1\le L\le 1000, 1≤Ai≤10001\le A_i\le 1000。

子任务 1(5 分)   N≤8\ \ N\le 8。
子任务 2(15 分)   N≤14,\ \ N\le 14, L≤100L\le 100。
子任务 3(80 分)   \ \ 没有额外限制。