#P17795. JYPnation

JYPnation

CF1338E JYPnation

题目描述

由于 TWICE 的成功,JYP Entertainment 赚取了无数财富,并成为市值最大的娱乐公司。因此,老板 JYP 决定建立一个新国家,并任命你来提供设计图。

新国家由 nn 个城市和若干条连接它们的道路组成。JYP 给出了一些限制条件:

  • 为了保证效率并避免混乱,对于任意两个不同的城市 AA 和 BB,它们之间恰好有一条单向道路。不存在一座城市与自身相连的道路。
  • 竞争对手公司的标志不应出现在设计图中,即不存在 44 个不同的城市 AA、BB、CC、DD,使得下图所示的结构出现。

JYP 对你的设计图提出了如下评判标准。对于两个城市 AA、BB,定义 dis(A,B)dis(A,B) 为从 AA 到 BB 需要经过的最少道路数。如果无法从 AA 走到 BB,则 dis(A,B)=614ndis(A,B) = 614n。那么,效率值定义为所有有序不同城市对 (A,B)(A,B) 的 dis(A,B)dis(A,B) 之和。

注意,dis(A,B)dis(A,B) 不一定等于 dis(B,A)dis(B,A)。

你已经画出了满足 JYP 限制条件的设计图。请计算所有有序不同城市对 (A,B)(A,B) 的 dis(A,B)dis(A,B) 之和。

注意,输入是压缩格式的。即使输入经过压缩,建议你使用快速输入。

输入格式

第一行包含一个整数 nn(4≤n≤80004 \le n \le 8000,n≡0(mod4)n \equiv 0 \pmod{4}),表示城市的数量。

接下来的 nn 行,每行包含 n4\frac{n}{4} 个一位十六进制数(这些数字可以是 00 到 99,或大写字母 AA 到 FF)。每个数字的二进制表示对应该行接下来的 44 个矩阵元素。例如,如果给出数字 BB,则对应的元素为 10111011,如果是 55,则为 01010101。

解密得到二进制矩阵后,第 ii 行第 jj 个字符为 11,表示从城市 ii 到城市 jj 有一条单向道路,否则为 00。保证给出的图满足上述所有限制条件。

输出格式

输出一个整数,表示所有有序不同城市对 (A,B)(A,B) 的 dis(A,B)dis(A,B) 之和。

输入输出样例 #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$

dis(2,4)=dis(4,3)=dis(3,2)=2dis(2,4)=dis(4,3)=dis(3,2)=2

dis(2,1)=dis(3,1)=dis(4,1)=2456dis(2,1)=dis(3,1)=dis(4,1)=2456

因此该设计图的答案为 73807380。