CF1338E JYPnation

由于 TWICE 的成功，JYP Entertainment 赚取了无数财富，并成为市值最大的娱乐公司。因此，老板 JYP 决定建立一个新国家，并任命你来提供设计图。 新国家由 $n$ 个城市和若干条连接它们的道路组成。JYP 给出了一些限制条件： - 为了保证效率并避免混乱，对于任意两个不同的城市 $A$ 和 $B$，它们之间恰好有一条单向道路。不存在一座城市与自身相连的道路。 - 竞争对手公司的标志不应出现在设计图中，即不存在 $4$ 个不同的城市 $A$、$B$、$C$、$D$，使得下图所示的结构出现。  JYP 对你的设计图提出了如下评判标准。对于两个城市 $A$、$B$，定义 $dis(A,B)$ 为从 $A$ 到 $B$ 需要经过的最少道路数。如果无法从 $A$ 走到 $B$，则 $dis(A,B) = 614n$。那么，效率值定义为所有有序不同城市对 $(A,B)$ 的 $dis(A,B)$ 之和。 注意，$dis(A,B)$ 不一定等于 $dis(B,A)$。 你已经画出了满足 JYP 限制条件的设计图。请计算所有有序不同城市对 $(A,B)$ 的 $dis(A,B)$ 之和。 注意，输入是压缩格式的。即使输入经过压缩，建议你使用快速输入。

第一行包含一个整数 $n$（$4 \le n \le 8000$，$n \equiv 0 \pmod{4}$），表示城市的数量。 接下来的 $n$ 行，每行包含 $\frac{n}{4}$ 个一位十六进制数（这些数字可以是 $0$ 到 $9$，或大写字母 $A$ 到 $F$）。每个数字的二进制表示对应该行接下来的 $4$ 个矩阵元素。例如，如果给出数字 $B$，则对应的元素为 $1011$，如果是 $5$，则为 $0101$。 解密得到二进制矩阵后，第 $i$ 行第 $j$ 个字符为 $1$，表示从城市 $i$ 到城市 $j$ 有一条单向道路，否则为 $0$。保证给出的图满足上述所有限制条件。

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

第一个样例对应的矩阵为： $\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)=2$ $dis(2,1)=dis(3,1)=dis(4,1)=2456$ 因此该设计图的答案为 $7380$。 由 ChatGPT 4.1 翻译