Make Pair
dp[l][r]: 生徒 l, l + 1, ..., r - 1 をペアにする操作方法の通り数
初期値: dp[i][i] = 1
答え: dp[0][n * 2]
漸化式は次のようになる
生徒 l と生徒 l + 1, l + 3, l + 5, ... をペアにすることを考える
生徒 l とペアになる生徒を k とおこう
生徒 l + 1, l + 2, ..., k - 1 をペアにする通り数は dp[l + 1][k]
生徒 k + 1, k + 2, ..., r - 1 をペアにする通り数は dp[k + 1][r]
[l, r) 内の操作順は binom((r - l) / 2, (r - (k + 1)) / 2) 通り
実際、操作順は [l, r) への操作 (r - l) / 2 個のうち、
[k + 1, r) への操作 (r - (k + 1)) / 2 個をいつ行うか決めれば、残りはひとつに決まる
特に、生徒 l と生徒 k をペアにする操作は [l + 1, k) への操作をすべて終えた後に行うことに注意する
([l + 1, k) を全部消した後でないと l と k は隣り合わないため)
結局、漸化式は dp[l][r] = sum(dp[l + 1][k] * dp[k + 1][r] * binom((r - l) / 2, (r - (k + 1)) / 2)) となる
k は l + 1, l + 3, l + 5, ... のうち l と仲が良い数全体を走る