← 返回题目列表

Codeforces · 1338/E

E. JYP国度

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

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

新国家由 $$$n$$$ 个城市和城市之间的一些道路组成。 JYP给出了一些限制:

- 为了保证效率,避免混乱,对于任何$$$2$$$不同的城市$$$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)$$$ 与 $$$A\neq 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$$$之间的单向道路是从$$$i$$$到$$$j$$$,则第$$$i$$$行的第$$$j$$$字符为$$$1$$$,否则为$$$0$$$。保证该图满足上述限制。

输出

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

示例

输入 #1

4
7
2
1
4

输出 #1

7380

输入 #2

8
7F
3F
1F
0C
06
03
11
18

输出 #2

88464

注意

第一个示例对应于矩阵:

$$$\开始{矩阵} 0111 \\ 0010 \\ 0001 \\ 0100 \\ \结束{矩阵}$$$

对应于该图:

$$$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$$$。