← 返回题目列表

AtCoder · agc039_e

E. 配对点

中文机器翻译题面 查看原题

分数: 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 0 or 1.
  • 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