[CEOI2010 day2] tower

题目背景

古巴比伦人决定建造一座塔。

题目描述

这座塔共有 \(n\) 层，每层由一个边长为 \(a_i\) 的立方体石块构成。一个石块 \(i\) 能够直接放在石块 \(j\) 上当且仅当 \(a_i \leq a_j+D\)，其中 \(D\) 为一个给定的常数。

你需要求出如果使用全部的石块，有多少种不同的搭建方案。输出答案 \(\bmod\ 10^9+9\) 的结果。

注意：即使两个石块的边长相同，也看做不同的石块。

输入格式

输入第一行两个整数 \(n,D\)。

第二行 \(n\) 个整数 \(a_1,\dots,a_n\)，表示每个立方体石块的边长。

输出格式

输出一行一个整数，表示方案总数 \(\bmod\ 10^9+9\) 的结果。

样例 #1

样例输入 #1

4 1
1 2 3 100

样例输出 #1

4

样例 #2

样例输入 #2

6 9
10 20 20 10 10 20

样例输出 #2

36

提示

【样例解释】

样例 1 解释

首先把边长为 \(100\) 的石块放在底部，其余的石块可以任意顺序放置，除了以下两种情况：2,1,3 1,3,2。

样例 2 解释

首先不允许在 \(10\) 上面放 \(20\)。

所以就把 \(20\) 一堆放在底下，\(10\) 一堆放在上面。

即 \((3!)\times (3!)=36\)。

【数据规模与约定】

• 对于 \(10\%\) 的数据，保证 \(n\le 10\)；
• 对于 \(30\%\) 的数据，保证方案数不超过 \(10^6\)；
• 对于 \(45\%\) 的数据，保证 \(n\le 20\)；
• 对于 \(70\%\) 的数据，保证 \(n\le 70\)；
• 对于 \(100\%\) 的数据，保证 \(2\le n\le 6.2\times 10^5\)，输入中所有数字为不超过 \(10^9\) 的正整数。

【说明】

题目译自 CEOI 2010 day 2 T3 tower。

翻译版权为题目提供者 @ShineEternal 所有，未经许可禁止转载。