AT_agc039_e [AGC039E] Pairing Points

[problemUrl]: https://atcoder.jp/contests/agc039/tasks/agc039_e 円周上の一般の位置に相異なる $ 2N $ 個の点が並んでおり、反時計回りに順に $ 1,\dots,2N $ の番号が付けられています。 ただし、ここでいう一般の位置とは、どの相異なる $ 6 $ 点 $ U,\ V,\ W,\ X,\ Y,\ Z $ についても、線分 $ UV,\ WX,\ YZ $ が一点で交わらないことをいいます。 また、 $ 2N\ \times\ 2N $ の行列 $ A $ が与えられます。 円周上の $ 2N $ 個の点を $ N $ 個のペアに分ける方法であって、以下の条件をみたすようなものの個数を求めてください。 - すべてのペアに対してそのペアの $ 2 $ つの点を結ぶ赤い線分をひいたとき、赤い部分が "木" になっている。 - すべてのペアについて、その端点を点 $ P,\ Q $ としたとき、 $ A_{P,Q}\ =\ A_{Q,P}\ =\ 1 $ である。 より厳密には、赤い部分が "木" になっているとは、赤い部分全体が連結かつ無閉路になっていることを指します。 例えば、下図において、 - 左上の例は条件を満たします。 - 右上の例は、赤い部分に閉路が存在し、条件を満たしません。 - 左下の例は、赤い部分が非連結であり、条件を満たしません。 - 右下の例は、ペアに属さない頂点やペアに複数回含まれる頂点が存在し、条件を満たしません。 図: 条件を満たす例 (左上) とそうでない例 (それ以外)

N/A

N/A

### ノート 答えは、$ 2N $ 個の点が一般の位置にある限り、その具体的な位置関係には依存しないことが証明できます。 ### 制約 - $ 1\ \leq\ N\ \leq\ 20 $ - $ A_{i,j} $ は `0` または `1` である - $ A_{i,i} $ は `0` である - $ A_{i,j}=A_{j,i} $ - $ N $ は整数である ### Sample Explanation 1 $ ((1,4),(2,6),(3,5)) $, $ ((1,3),(2,5),(4,6)) $, $ ((1,5),(2,4),(3,6)) $ の $ 3 $ つの分け方が条件を満たします。