← 完整题目索引

PROJECT EULER · #0716

网格图

Grid Graphs

仅题目 · 待解原题 ↗

考虑由 H×W 个节点的正交格组成的有向图。 边是相邻节点之间的水平和垂直连接。 绘制 W 垂直有向线,这些线上的所有边缘都继承该方向。类似地,绘制 H 水平有向线,并且这些线上的所有边缘都继承该方向。

如果有向图中沿着有向边同时存在从 AB 以及从 BA 的路径,则有向图中的两个节点 AB强连接的。请注意,每个节点都与其自身强连接。

有向图中的强连通分量是满足以下两个属性的非空节点集 M

  • M 中的所有节点都彼此强连接。
  • M 是最大的,即 M 中没有节点与 M 之外的任何节点强连接。

绘制有向线的方法有 2H×2W 种。每种方式都给出一个有向图G。我们定义S(G)G中强连通分量的数量。

下图显示了 H=3W=4 的有向图,它由四个不同的强连通分量组成(用不同的颜色表示)。

C(H,W) 定义为 H×W 网格上所有可能图形的 S(G) 之和。您将得到 C(3,3)=408C(3,6)=4696C(10,20)988971143(mod1000000007)

找到 C(10000,20000),给出你的答案模 1000000007

题解待补充

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