Yukicoder No.727 仲介人moko
解法
DP。 列中の$2N$個の要素をまったく前から順に埋めていくのではなく、まだ埋めてない要素に注目する感じでやる。 $2N!! \cdot (N!)^2$が答え。$O(N)$。
$N!$をそれぞれ後で書けることにして売りたい人も買いたい人も番号順に来るとしてよい。
誰が売った品物を誰が買うのか、売りたい人と買いたい人がどのような混ざり方で来るか、このふたつを数える。
長さ$2N$の列を、買う人と売る人の組をまとめて埋めていく。
売る人はまだ埋めてない位置の最も左に来るしかなくて、例えば 12...1...2..
のように$2$組分を埋めてから$3$組目を考えるなら可能性は 1233.1...2..
123.31...2..
123..13..2..
$\dots$ 123..1...2.3
の$7$通り。
これは埋まってない位置だけ考えれば十分なのでDPで解ける。
さらに整理すると $(2N - 1) \cdot (2N - 3) \cdot \dots 1 = 2N!!$ になる。
メモ
なぜかまったく分からなかったです。でも典型
実装
#!/usr/bin/env python3
import random
MOD = 10 ** 9 + 7
n = int(input())
a = 1
for i in range(n):
a = a * (2 * i + 1) * (i + 1) ** 2 % MOD
print(a)