Public Judge

pjudge

Time Limit: 1 s Memory Limit: 1024 MB Total points: 100

# 21858. 【NOIP Round #7】排列计数

Statistics

给定一个正整数序列 $a_1,a_2,...,a_n(a_1 < a_2 < ... < a_n)$,序列中没有相同的元素。

求有多少个 $1\sim n$ 的排列 $p_1,\dots,p_n$,满足对所有 $1≤i≤n−1$,有 $|a_{p_i} - a_{p_{i+1}}| \ne k$,答案在模 $998244353$ 意义下输出。

输入格式

第一行两个整数 $n,k$。

第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$。

输出格式

输出一行一个整数表示答案。

输入输出样例

样例输入 1

4 1
1 2 3 4

样例输出 1

2

样例解释 1

$3,1,4,2$ 和 $2,4,1,3$ 满足条件。

样例输入输出 2,3

见下发文件。

数据范围

对于所有数据,有:

  • $1 \le n \le 5 \times 10^3$
  • $1 \le k \le 10^6$
  • $1 \le a_i \le 10^9$
子任务编号 特殊性质 分值
$1$ $n \le 10$ $20$
$2$ $n \le 400$ $30$
$3$ $n \le 1000$ $20$
$4$ 无特殊性质 $30$