{"problem":{"name":"[JOI Open 2016] 摩天大楼 / Skyscraper","description":{"content":"将互不相同的 $N$ 个整数 $A_1, A_2, \\cdots, A_N$ 按照一定顺序排列。 假设排列为 $f_1, f_2, \\cdots, f_N$，要求：$| f_1 - f_2| + | f_2 - f_3| + \\cdots + | f_{N-1} - f_N| \\leq L$。 求满足题意的排列的方案数对 $10^9+7$ 取模后的结果。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9197"},"statements":[{"statement_type":"Markdown","content":"将互不相同的 $N$ 个整数 $A_1, A_2, \\cdots, A_N$ 按照一定顺序排列。\n\n假设排列为 $f_1, f_2, \\cdots, f_N$，要求：$| f_1 - f_2| + | f_2 - f_3| + \\cdots + | f_{N-1} - f_N| \\leq L$。\n\n求满足题意的排列的方案数对 $10^9+7$ 取模后的结果。\n\n## Input\n\n输入共两行。\n\n第一行有两个整数 $N, L$。  \n第二行有 $N$ 个整数 $A_1, A_2, \\cdots, A_N$。\n\n## Output\n\n输出共一行一个整数，表示方案数对 $10^9+7$ 取模后的结果。\n\n[samples]\n\n## Background\n\n**译自 [JOI Open 2016](https://contests.ioi-jp.org/open-2016/index.html) T3 「高層ビル街 / Skyscraper」**\n\n## Note\n\n### 样例 1 解释\n\n满足条件的六种方案分别为：\n$$\n\\begin{matrix}\n2\\ 3\\ 6\\ 9,& |2 - 3| + |3 - 6| + |6 - 9| &=& 7 \\\\\n2\\ 3\\ 9\\ 6,& |2 - 3| + |3 - 9| + |9 - 6| &=& 10 \\\\\n3\\ 2\\ 6\\ 9,& |3 - 2| + |2 - 6| + |6 - 9| &=& 8 \\\\\n6\\ 9\\ 3\\ 2,& |6 - 9| + |9 - 3| + |3 - 2| &=& 10 \\\\\n9\\ 6\\ 2\\ 3,& |9 - 6| + |6 - 2| + |2 - 3| &=& 8 \\\\\n9\\ 6\\ 3\\ 2,& |9 - 6| + |6 - 3| + |3 - 2| &=& 7 \\\\\n\\end{matrix}\n$$\n\n### 数据规模与约定\n\n**本题采用捆绑测试。**\n\n对于所有数据，$1\\le N\\le 100$，$1\\le L\\le 1000$，$1\\le A_i\\le 1000$。\n\n- Subtask 1（5 points）：$N\\le 8$。\n- Subtask 2（15 points）：$N\\le 14$，$L\\le 100$。\n- Subtask 3（80 points）：没有额外限制。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9197","tags":["动态规划 DP","2016","JOI（日本）"],"sample_group":[["4 10\n3 6 2 9","6"],["8 35\n3 7 1 5 10 2 11 6","31384"]],"created_at":"2026-03-03 11:09:25"}}