0%

Problem 716


Problem 716


Grid Graphs

Consider a directed graph made from an orthogonal lattice of $H\times W$ nodes. The edges are the horizontal and vertical connections between adjacent nodes. $W$ vertical directed lines are drawn and all the edges on these lines inherit that direction. Similarly, $H$ horizontal directed lines are drawn and all the edges on these lines inherit that direction.

Two nodes, $A$ and $B$ in a directed graph, are strongly connected if there is both a path, along the directed edges, from $A$ to $B$ as well as from $B$ to $A$. Note that every node is strongly connected to itself.

A strongly connected component in a directed graph is a non-empty set $M$ of nodes satisfying the following two properties:

  • All nodes in $M$ are strongly connected to each other.
  • $M$ is maximal, in the sense that no node in $M$ is strongly connected to any node outside of $M$.

There are $2^H\times 2^W$ ways of drawing the directed lines. Each way gives a directed graph $\mathcal{G}$. We define $S(\mathcal{G})$ to be the number of strongly connected components in $\mathcal{G}$.

The illustration below shows a directed graph with $H=3$ and $W=4$ that consists of four different strongly connected components (indicated by the different colours).

Define $C(H,W)$ to be the sum of $S(\mathcal{G})$ for all possible graphs on a grid of $H\times W$. You are given $C(3,3) = 408$, $C(3,6) = 4696$ and $C(10,20) \equiv 988971143 \pmod{1\ 000\ 000\ 007}$.

Find $C(10\ 000,20\ 000)$ giving your answer modulo $1\ 000\ 000\ 007$.


格阵图

考虑一张基于$H\times W$个结点组成的格阵所构成的有向图,图中的边水平或竖直连接着相邻的结点。在格阵上可以画出$W$条竖直的有向直线,所有落在直线上的边和相应直线的方向一致;同理,在格阵上可以画出$H$条水平的有向直线,所有落在直线上的边和相应直线的方向也一致。

在有向图中,如果在两个结点$A$和$B$之间,存在一条沿着有向边由$A$到$B$的路径,同时也存在一条沿着有向边由$B$到$A$的路径,则称这两个结点是强连通的。注意每个结点和其自身都是强连通的。

有向图中的一个强连通分支是指满足以下两条性质的非空结点集$M$:

  • $M$中的任意两个结点之间都是强连通的。
  • $M$是极大的,这意味着不存在$M$之内的结点和$M$之外的结点之间是

共有$2^H\times 2^W$种绘制有向直线的方式,每种方式确定了一张有向图$\mathcal{G}$。记$S(\mathcal{G})$为$\mathcal{G}$中强连通分支的数目。

下图展示了$H=3$、$W=4$时的一张有向图,这张图有四个不同的强连通分支(用不同颜色表示)。

记$C(H,W)$为所有基于$H\times W$的格阵的有向图对应$S(\mathcal{G})$之和。已知$C(3,3) = 408$,$C(3,6) = 4696$,$C(10,20) \equiv 988971143 \pmod{1\ 000\ 000\ 007}$。

求$C(10\ 000,20\ 000)$并将你的答案对$1\ 000\ 000\ 007$取余。