bzoj#P4352. Tower

Tower

题目描述

你要用 nn 个积木拼成一个塔,第 ii 块积木长度是 aia_i

给定 DD,积木 ii 能搭在积木 jj 上面,当且仅当 aiajDa_i-a_j\le D

求合法的搭积木方案数对 998244353998244353 取模后的结果。

输入格式

第一行两个整数 n,Dn,D。表示积木的数量和搭建的限制。

第二行 nn 个整数 aia_i,表示每块积木的长度。

输出格式

一行一个整数,表示搭积木的方案数对 998244353998244353 取模后的结果。

4 1
1 2 3 100
4

提示

样例解释:最后一个积木只能在下面,考虑前 33 个积木,(1,2,3),(2,3,1),(3,1,2),(3,2,1)(1,2,3),(2,3,1),(3,1,2),(3,2,1) 都是合法的。

对于100%100\% 的数据,满足 1n7×1051\le n\le 7\times 10^5

题目来源

没有写明来源