E - ≥ K Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 800 点

問題文

長さ N の数列 A = (A_1, ..., A_N) および整数 K が与えられます。
A の要素を並べ替えて得られる数列のうち、隣接する要素の和が K より小さい箇所が存在しない数列は何通りありますか？個数を 998244353 で割ったあまりを求めてください。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 0 \leq K \leq 10^9
  • 0 \leq A_i \leq 10^9
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N K
A_1 A_2 \dots A_N

出力

答えを出力せよ。

入力例 1

4 5
1 2 3 4

出力例 1

4

条件を満たす数列は次の 4 通りです。

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

入力例 2

4 3
1 2 3 3

出力例 2

12

A の要素を並べ替えてできる数列としてあり得るのは全部で 12 通りあり、その全てが条件を満たします。

入力例 3

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

出力例 3

108

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