bzoj#P2013. [CEOI2010] A huge tower

[CEOI2010] A huge tower

题目描述

nn 块砖,要搭一个 nn 层的塔,要求:如果砖 aa 在砖 bb 上面,那么 aa 不能比 bb 的长度 +d+ d 要长。问有几种方法,输出答案 mod 109+9\bmod\ 10^9+9 的值。

输入格式

第一行:n,dn,d

第二行:nn 个数,表示每块砖的长度。

输出格式

方案数。输出要 mod 109+9\bmod\ 10^9+9

4 1
1 2 3 100
4

样例说明 1

We can arrange the first three blocks in any order, except for 2,1,32,1,3 or 1,3,21,3,2. The last block has to be at the bottom.

6 9
10 20 20 10 10 20
36

样例说明 2

We are not allowed to put a cube of size 2020 onto a cube of size 1010.

There are six ways to order the cubes of size 1010, and six ways to order the cubes of size 2020.

数据规模与约定

对于 10%10\% 的数据,n10n \leq 10

对于 30%30\% 的数据,方案数不超过 10610^6

对于 45%45\% 的数据,n20n \leq 20

对于 70%70\% 的数据,n70n \leq 70

对于 100%100\% 的数据,2n6.2×105 2 \leq n \leq 6.2\times 10^5,输入中所有数字为不超过 10910^9 的正整数。