No.727 仲介人moko - yukicoder

解は Π_{0<=i<N}{H(i*2+1, 2)(N-i)2} / N!

ただし、Πは総乗、H(n, r) = C(n+r-1, r) とする。

これは以下のように得る。残った売り手買い手から1人ずつ選んでペアを作り、既存の順番に挿入するということを繰り返すことを考える。 既存の順番がi個のペアをすでに作っているとする。この時、売り手、買い手の選び方が(N-i)2通り。この2人をどこに挿入するか。既存の列は2i人を含み、その間と端に重複を許して2人を挿入するのでH(2i+1, 2)通り。 あとは挿入順を無視するためにN!で割る。

namespace comb {
    const int N = 2000006;
    mint fact[N];
    mint rev[N];

    void init() {
        fact[0] = 1;
        for (int i = 1; i < N; ++i)fact[i] = fact[i - 1] * i;
        for (int i = 0; i < N; ++i)rev[i] = fact[i].inverse();
    }

    mint C(int n, int r) {
        if (n < r)return 0;
        return fact[n] * rev[r] * rev[n - r];
    }

    mint H(int n, int r) {
        return C(n + r - 1, r);
    }

    mint P(int n, int r) {
        assert(n >= r);
        return fact[n] * rev[n - r];
    }

    mint catalan(int n) {
        return fact[2 * n] * rev[n + 1] * rev[n];
    }
}

void solve() {
    comb::init();

    int N;
    cin >> N;
    mint re = comb::rev[N];
    rep(i, N) re *= comb::H(2 * i + 1, 2) * (N - i)*(N - i);
    cout << re << endl;
}