← 完整题目索引

PROJECT EULER · #0690

猫和老鼠

Tom and Jerry

仅题目 · 待解原题 ↗

汤姆(猫)和杰瑞(老鼠)正在玩一个简单的图表 G

G 的每个顶点都是一个鼠洞,G 的每条边都是连接两个鼠洞的隧道。

最初,杰瑞躲在其中一个老鼠洞里。
每天早上,汤姆都可以检查一个(而且只有一个)鼠洞。如果杰瑞碰巧躲在那里,那么汤姆就会抓住杰瑞,游戏就结束了。
每天晚上,如果游戏继续,杰瑞就会移动到与他当前藏身处相邻的鼠洞(即通过隧道连接,如果有的话)。第二天早上汤姆再次检查,游戏就这样继续进行。

让我们将图 G 称为 Tom 图,如果我们超级聪明的 Tom(知道图的配置但不知道 Jerry 的位置)可以保证在有限的许多天内抓住 Jerry。 例如,考虑 3 个节点上的所有图:

Graphs on 3 nodes

对于图 1 和图 2,汤姆最多三天就能追上杰瑞。对于图3,汤姆可以连续两天检查中间连接,因此保证最多两天赶上杰瑞。因此,这三个图是汤姆图。然而,图 4 不是 Tom 图,因为游戏可能会永远持续下去。

T(n) 为具有 n 个顶点的不同 Tom 图的数量。如果两个图的顶点之间存在双射 f,则两个图被认为是相同的,使得 (v,w) 是一条边当且仅当 (f(v),f(w)) 是一条边。

我们有 T(3)=3T(7)=37T(10)=328T(20)=1416269

找到 T(2019),将答案模 1000000007

题解待补充

这道题的题目已收录,解题思路、代码和答案将在后续补充。