CF1809G.Prediction
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Consider a tournament with n participants. The rating of the i -th participant is ai .
The tournament will be organized as follows. First of all, organizers will assign each participant an index from 1 to n . All indices will be unique. Let pi be the participant who gets the index i .
Then, n−1 games will be held. In the first game, participants p1 and p2 will play. In the second game, the winner of the first game will play against p3 . In the third game, the winner of the second game will play against p4 , and so on — in the last game, the winner of the (n−2) -th game will play against pn .
Monocarp wants to predict the results of all n−1 games (of course, he will do the prediction only after the indices of the participants are assigned). He knows for sure that, when two participants with ratings x and y play, and ∣x−y∣>k , the participant with the higher rating wins. But if ∣x−y∣≤k , any of the two participants may win.
Among all n! ways to assign the indices to participants, calculate the number of ways to do this so that Monocarp can predict the results of all n−1 games. Since the answer can be large, print it modulo 998244353 .
输入格式
The first line contains two integers n and k ( 2≤n≤106 ; 0≤k≤109 ).
The second line contains n integers a1,a2,…,an ( 0≤a1≤a2≤⋯≤an≤109 ).
输出格式
Print one integer — the number of ways to assign the indices to the participants so that Monocarp can predict the results of all n−1 games.
输入输出样例
输入#1
4 3 7 12 17 21
输出#1
24
输入#2
3 7 4 9 28
输出#2
4
输入#3
4 1 1 2 3 4
输出#3
0
输入#4
4 1 1 2 2 4
输出#4
12
输入#5
16 30 8 12 15 27 39 44 49 50 51 53 58 58 59 67 68 100
输出#5
527461297
说明/提示
In the first example, a match with any pair of players can be predicted by Monocarp, so all 24 ways to assign indices should be counted.
In the second example, suitable ways are [1,3,2] , [2,3,1] , [3,1,2 ] and [3,2,1] .