チーム戦 [yukicoder No.794] - はまやんはまやんはまやん

解説

https://yukicoder.me/submissions/319074

まず、Aはソート可能なのでソートする。
ペアを考えると、A「どちらもK/2以下」、B「片方K/2以下、もう片方K/2より大きい」になる。
重要なのが、AのペアとBのペアの個数は同じであるということ。
　
ここで、どっちの組み合わせから数えようかとなるが、AのペアはK/2以下から適当に選べるが、BのペアはK/2より大きい数によってK/2以下の選べる数が変わる。
なので、制約の厳しいBのペアから数え上げることにしよう。
　
Bのペアは大きい順からペアを決めていくことにする。
すると、ペアにできる相手は単調増加するので、ペアの数は今までどんなとり方をしても
(ペアにできる相手)-(既にペアが決まっている人数)
となる。
　
N人でペアを作る組み合わせはN!/(N/2)!/2^(N/2)で計算できるので、ペアAを残りで計算すると答え。

int N, K, A[201010];
mint dp[201010];
Comb<mint, 1010101> com;
//---------------------------------------------------------------------------------------------------
mint solve() {
    if (K <= A[N - 1]) return 0;

    if (A[N - 1] <= K / 2) return com.fac[N] / com.fac[N/2] / (mint(2)^(N/2));

    mint ans = 1;
    int L = 0;
    int used = 0;
    rrep(R, N - 1, 0) if (K / 2 < A[R]) {
        while (A[L] + A[R] <= K) L++;

        int cand = L;

        if (cand - used <= 0) return 0;
        ans *= mint(cand - used);
        used++;
    }

    int rest = N - used * 2;
    ans *= com.fac[rest] / com.fac[rest / 2] / (mint(2) ^ (rest / 2));
    return ans;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> A[i];
    sort(A, A + N);
    cout << solve() << endl;
}