\(A\) の要素が相異なる場合を解きます。(\(A\) に同じ数が含まれる場合も、同じ数を index で区別して順序付けを行えば同様の解法で解けます)

以下では「隣り合う要素の和が \(K\) 以上である数列」を valid な数列 と表現します。

次の手順によって \(A\) を並べ替えた valid な数列 \(B\) を得ることを考えます。

• 空の数列 \(B\) がある。次の操作を \(N\) 回行って、\(A\) の要素をすべて \(B\) に移し替えることを考える。
  • 現時点での \(A\) の最小値を \(L\), 最大値を \(R\) とする。\(L+R\) と \(K\) の大小で場合分けする。
    1. \(L+R \lt K\) ならば、\(L\) を \(A\) から取り除いて \(B\) の任意の箇所に挿入する。
    2. \(L+R \geq K\) ならば、\(R\) を \(A\) から取り除いて \(B\) の任意の箇所に挿入する。
  • ただし、いずれの場合も挿入直後の \(B\) は valid である必要がある。

この操作によって生成できる数列 \(B\) としてあり得るものの個数を考えます。
はじめに次の事実を確認します。

• \(B\) に \(L, R\) を挿入するとき、\(L \lt K/2, R \geq K/2\) が成り立つ。

これは場合分けの条件から直ちに成り立ちます。(それぞれ \(2L \leq L+R \lt K\), \(2R \geq L+R \geq K\))

さて、操作を \(i\) 回 \((0 \leq i \lt N)\) 行った時点で、\(B\) の長さは \(i\) です。このとき、次の条件を満たすような \(B_j\) と \(B_{j+1}\) の間 \((1 \leq j \leq i + 1)\) を 空間 と呼びます。(ただし便宜上 \(B_{0}=B_{i+1}=\infty\) とします)

• (現時点での\(\min A\)) \(+ \min(B_{i-1},B_i) \geq K\)

そして、\(i\) 回目の操作を行った後の \(B\) に含まれる空間の個数を \(S_i\) とおきます。(特に \(i=0\) の場合は、 \(B\) は空で \(S_0 = 1\) です。)

このとき、 \(A\) の要素を挿入する箇所は常に空間である事が示せます。

(略証) \(L\) を挿入する場合は空間の定義より明らかです。\(R\) を挿入する場合を考えます。\(i\) 回目に挿入した \(R\) が \(K/2 + d\) \((d \geq 0)\) と表せるとします。\(L+R \geq K\) より \(L \geq K/2 - d\) なので、\(j\) が空間に対応する index でない場合\(\min(B_{j}, B_{j+1})\) は \(K/2 + d\) より小さいです。また、この時点での \(B\) を構成する要素は \(K/2-d\) 未満と \(K/2 + d\) 以上からなります。よって空間でない箇所は \(\min(B_{j}, B_{j+1}) \lt K/2-d\) が成り立ち、\(R\) を挿入できません。

また、次の事実が示せます。

• \(i\) 回目に \(L\) を挿入した時、挿入の前後で空間は \(1\) 減る。
• \(i\) 回目に \(R\) を挿入した時、挿入の前後で空間は \(1\) 増える。

(略証) 前者は \(L \lt K/2\) から明らかです。後者については、\(i\) 回目に挿入した \(R\) が \(K/2 + d\) \((d \geq 0)\) と表せるとき、\(A\) に残っている \(K/2\) 未満の要素はすべて \(K/2 - d\) 以上であることから従います。

また、挿入する箇所に関わらず、\(i\) 番目に挿入する値は同じです。よって、どのような操作を行ったとしても \(S_0, S_1, S_2, \dots, S_N\) の列は常に一定なのが言えます。

以上の議論より、前述の操作によって生成される数列の個数は \(\prod_{i=0}^{N-1} S_i\) であるとわかりました。

ここで、\(i\) 回目の操作終了時点での \(B\) を \(C_i\) とおきます。\(N\) 回の操作全体は 長さ \(N+1\) の列 \((C_0, C_1, \dots, C_N)\) で表すことができます。以下ではこの操作全体を表す列を 操作列 と呼びます。
ここまでは 1 つの操作列から 1 つの数列を得る方法を得る方法を説明していました。実は、操作列によって生成される数列全体によって、 \(A\) を並べ換えてできる valid な数列は尽くされていることが示せます。
証明として、逆に 1 つの数列から 1 つの操作列を得る方法を説明します。隣接する要素の和が \(K\) 以下である \(A\) を並べ替えた列 \(B\) に対して、次の操作を \(N\) 回行って \(B\) を空にすることを考えます。

• \(B\) の要素 \(x\) のうち \(\vert K/2 - x \vert\) が最も小さい要素を選び、その要素を取り除く。(候補が複数ある場合は \(x\) 自体の値が小さいものを選ぶ)

このとき、操作の過程において \(B\) は常に valid であることが示せます。

(略証) \(d\geq 0\) とします。\(x=K/2-d\) を取り除く場合、\(x\) の両隣は \(K/2+d\) 以上なので取り除いても valid な状態が保たれます。 \(x=K/2+d\) を取り除く場合、\(B\) には \(K/2-d\) 未満と \(K/2 + d\) 以上のみが残っています。\(x\) と前者が隣り合っている場合は帰納的に矛盾が示せるので \(x\) は \(K/2 + d\) 以上と隣り合っている必要があり、取り除いても列は valid な状態です。

また、取り除く操作によって \(i\) 番目に取り除く要素は、挿入する操作によって \(N+1-i\) 番目に挿入する要素と一致することも確認できます。(証明略)

\(i\) 回取り除く操作を行ったあとの \(B\) を \(C_{N-i}\) とおきます。\(N\) 回の取り除く操作全体は長さ \(N+1\) の列 \((C_N, C_{N-1}, \dots, C_1, C_0)\) で表すことができます。上の論証から、この列を reverse したもの \((C_0, C_1, \dots, C_N)\) は操作列として合法であることが言えます。

以上より、操作列からなる集合と数列からなる集合の間で全単射を構成出来ました。よってこの問題の答えは \(\prod_{i=0}^{N-1} S_i\) です。実装はソートや std::map を利用すれば \(\mathrm{O}(N \log N)\) 程度で計算できて、これは十分高速です。

• 実装例(C++)

#include <algorithm>
#include <iostream>
#include <map>
using namespace std;
#include "atcoder/modint.hpp"
using mint = atcoder::modint998244353;

mint fac[200200] = {1}, ans = 1;
int N, K, A[200200], S = 1;
map<int, int> m;

int main() {
  cin >> N >> K;
  for (int i = 0; i < N; i++) cin >> A[i], m[A[i]]++;
  for (int i = 1; i <= N; i++) fac[i] = fac[i - 1] * i;
  sort(A, A + N);
  for (int i = 0, j = N - 1; i <= j;) {
    if (A[i] + A[j] < K) {
      ans *= S--, i++;
    } else {
      ans *= S++, j--;
    }
  }
  for (auto& [_, v] : m) ans /= fac[v];
  cout << ans.val() << "\n";
}