QOJ.ac

QOJ

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

题目描述

给一个正整数序列 $a_1,a_2,...,a_n(a_1 < a_2 < ... < a_n)$,求有多少种这个序列的排列 $\{p_n\}$ 满足对所有 $1\leq i\leq n-1$,有 $|p_i-p_{i+1}|\neq k$,答案模 $998244353$。

输入格式

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

第二行 $n$ 个正整数 $a_1,a_2,...,a_n$。

输出格式

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

样例输入 1

4 1
1 2 3 4

样例输出 1

2

样例解释 1

只有 $3,1,4,2$ 和 $2,4,1,3$ 两种排列满足条件。

样例输入 2

7 2
1 2 3 4 6 7 8

样例输出2

1272

数据范围

保证 $n\leq 5\times 10^3,k\leq 10^6,a_i\leq 10^9$ 。

subtask1(20pts):保证 $n\leq 10$ 。

subtask2(30pts):保证 $n\leq 400$ 。

subtask3(20pts):保证 $n\leq 1000$ 。

subtask4(30pts):无特殊限制