Two Arrays - Educational Codeforces Round 80 div2 c

#math #言い換え #場合の数

問題
https://codeforces.com/contest/1288/problem/C

解法

$a_1 ≤ a_2 ≤ ... ≤ a_m ≤ b_m ≤ b_{m - 1} ≤ ... ≤ b_1$
$a_1 < a_2 + 1 < a_3 + 2 ... < a_m + (m - 1) ≤ b_m + m < b_{m - 1} + (m + 1) < ... < b_1 + (2m - 1)$

対応するように,
$c_1 < c_2 < c_3 < ... < c_{2m}$

$1 ≤ a_i, b_i ≤ n$ より, $1 ≤ c_i ≤ n + (2m - 1)$

$c_i$ が決まれば $a_j, b_k$ も 1 対 1 で決まる

答えは, ${}_{2m - 1 + n} C_{2m}$

コード
https://codeforces.com/contest/1288/submission/68889748