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; }