QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 1024 MB Total points: 100
[+4]

# 8351. Ruin the legend

Statistics

题目描述

给一个正整数序列 a1,a2,...,an(a1<a2<...<an),求有多少种这个序列的排列 {pn} 满足对所有 1in1,有 |pipi+1|k,答案模 998244353

输入格式

第一行两个正整数 n,k,分别代表序列中的元素个数和限制中 k 的值。

第二行 n 个正整数 a1,a2,...,an

输出格式

一行一个正整数,代表满足要求的排列个数。

样例输入 1

4 1
1 2 3 4

样例输出 1

2

样例解释 1

只有 3,1,4,22,4,1,3 两种排列满足条件。

样例输入 2

7 2
1 2 3 4 6 7 8

样例输出2

1272

数据范围

保证 n5×103,k106,ai109

subtask1(20pts):保证 n10

subtask2(30pts):保证 n400

subtask3(20pts):保证 n1000

subtask4(30pts):无特殊限制