201484: [AtCoder]ARC148 E - ≥ K

Memory Limit：1024 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

Score : $800$ points

Problem Statement

You are given a sequence of length $N$, $A = (A_1, ..., A_N)$, and an integer $K$.
How many permutations of $A$ are there such that no two adjacent elements sum to less than $K$? Find the count modulo $998244353$.

Constraints

  • $2 \leq N \leq 2 \times 10^5$
  • $0 \leq K \leq 10^9$
  • $0 \leq A_i \leq 10^9$
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$N$ $K$
$A_1$ $A_2$ $\dots$ $A_N$

Output

Print the answer.

Sample Input 1

4 5
1 2 3 4

Sample Output 1

4

The following four permutations satisfy the condition:

  • $(1, 4, 2, 3)$
  • $(1, 4, 3, 2)$
  • $(2, 3, 4, 1)$
  • $(3, 2, 4, 1)$

Sample Input 2

4 3
1 2 3 3

Sample Output 2

12

There are $12$ permutations of $A$, all of which satisfy the condition.

Sample Input 3

10 7
3 1 4 1 5 9 2 6 5 3

Sample Output 3

108

Input

题意翻译

#### 题目描述 给定长度为 $n$ 的数列 $\{a_i\}$ 和一个自然数 $K$, 可以将 $\{a_i\}$ 打乱顺序重排，问多少种结果序列满足 $\forall i \in [1,n), a'_i + a'_{i+1} \ge K$。 答案对 $998244353$ 取模。 #### 输入格式 $n\ \ K$ $a_1\ \ a_2\ ... \ a_n$ #### 输出格式 一个整数，答案对 $998244353$ 取模的结果。 ##### 样例解释1 共 $4$ 个：$ (1,\ 4,\ 2,\ 3) - (1,\ 4,\ 3,\ 2)- (2,\ 3,\ 4,\ 1) - (3,\ 2,\ 4,\ 1)$ #### 数据范围 $ 2 \le n \le 2 \times 10^5$ $ 0 \le a_i, K \le 10^9$

Source/Category

加入题单

算法标签：