#PQJ1644x8351. QOJ 1644_8351

    ID: 2676 传统题 1000ms 1024MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:IOI 2022 集训动态规划

QOJ 1644_8351

标题: Ruin the legend - Problem - QOJ.ac

#8351. Ruin the legend

Statistics

The problem was used in the following contests:

题目描述

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

输入格式

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

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

输出格式

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

样例输入 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≤5×103,k≤106,ai≤109 。

subtask1(20pts):保证 n≤10 。

subtask2(30pts):保证 n≤400 。

subtask3(20pts):保证 n≤1000 。

subtask4(30pts):无特殊限制