分数: 1500 点
问题陈述
有 2N 点 一般定位 在圆的圆周上,编号 1,\dots,2N 按逆时针顺序。 这里,如果对于任何六个不同的点,则称一组点被普遍定位 U, V, W, X, Y, 和 Z 其中,段 UV, WX, 和 YZ 不相交于同一点。 此外,您还将获得一个 2N\times 2N 矩阵 A.
求除法的数目 2N 指向 N 配对,以满足以下所有条件:
- 让我们画一条红色线段连接每对的两个点。然后,那些红色的部分 形成一棵树.
- 对于每对 (P, Q), A_{P,Q} = A_{Q,P} = 1 成立。
这里,如果一组线段全部连接并且不形成环,则称它们形成一棵树。
例如见下图:
- 左上:满足条件。
- 右上:红色线段形成一个循环,因此条件不满足。
- 左下:红色线段没有连接,所以条件不满足。
- 右下:有些顶点属于无对或多对,因此不满足条件。
图:满足条件的部门(左上)和违反条件的部门(其他)
注释
可以证明,只要 2N 点一般都有定位,答案并不取决于它们的具体位置。
约束
- 1 \leq N \leq 20
- A_{i,j} is
0or1. - A_{i,i} is
0. - A_{i,j}=A_{j,i}
- N 是一个整数。
输入
输入由标准输入按以下格式给出:
N
A_{1,1}...A_{1,2N}
:
A_{2N,1}...A_{2N,2N}
输出
打印划分的方式数 2N 指向 N 配对以满足所有条件。 可以证明答案符合 64- 在给定约束下的位有符号整数。
样本输入 1
3 011111 101111 110111 111011 111101 111110
示例输出 1
3
满足条件的可能划分有以下三种: ((1,4),(2,6),(3,5)), ((1,3),(2,5),(4,6)),和 ((1,5),(2,4),(3,6)).
示例输入 2
4 01111100 10011111 10011100 11101111 11110111 11111011 01011101 01011110
示例输出 2
6
示例输入 3
8 0111101111111111 1011101111111111 1101101111011101 1110111111111111 1111011111110111 0001101111111111 1111110111011111 1111111011111111 1111111101111111 1111111110111111 1101110111011111 1111111111101111 1111011111110111 1111111111111011 1101111111111101 1111111111111110
示例输出 3
4762