#P17795. JYPnation
JYPnation
CF1338E JYPnation
题目描述
由于 TWICE 的成功,JYP Entertainment 赚取了无数财富,并成为市值最大的娱乐公司。因此,老板 JYP 决定建立一个新国家,并任命你来提供设计图。
新国家由 个城市和若干条连接它们的道路组成。JYP 给出了一些限制条件:
- 为了保证效率并避免混乱,对于任意两个不同的城市 和 ,它们之间恰好有一条单向道路。不存在一座城市与自身相连的道路。
- 竞争对手公司的标志不应出现在设计图中,即不存在 个不同的城市 、、、,使得下图所示的结构出现。

JYP 对你的设计图提出了如下评判标准。对于两个城市 、,定义 为从 到 需要经过的最少道路数。如果无法从 走到 ,则 。那么,效率值定义为所有有序不同城市对 的 之和。
注意, 不一定等于 。
你已经画出了满足 JYP 限制条件的设计图。请计算所有有序不同城市对 的 之和。
注意,输入是压缩格式的。即使输入经过压缩,建议你使用快速输入。
输入格式
第一行包含一个整数 (,),表示城市的数量。
接下来的 行,每行包含 个一位十六进制数(这些数字可以是 到 ,或大写字母 到 )。每个数字的二进制表示对应该行接下来的 个矩阵元素。例如,如果给出数字 ,则对应的元素为 ,如果是 ,则为 。
解密得到二进制矩阵后,第 行第 个字符为 ,表示从城市 到城市 有一条单向道路,否则为 。保证给出的图满足上述所有限制条件。
输出格式
输出一个整数,表示所有有序不同城市对 的 之和。
输入输出样例 #1
输入 #1
4
7
2
1
4
输出 #1
7380
输入输出样例 #2
输入 #2
8
7F
3F
1F
0C
06
03
11
18
输出 #2
88464
说明/提示
第一个样例对应的矩阵为:
$\begin{matrix} 0111 \\ 0010 \\ 0001 \\ 0100 \\ \end{matrix}$
对应的图如下:

$dis(1,2)=dis(1,3)=dis(1,4)=dis(2,3)=dis(3,4)=dis(4,2)=1$
因此该设计图的答案为 。