시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 45 | 24 | 22 | 52.381% |
Now Elsie creates a new undirected graph $G$ with $N_1\cdot N_2\cdots N_K$ vertices, each labeled by a $K$-tuple $(j_1,j_2,\ldots,j_K)$ where $1\le j_i\le N_i$. In $G$, two vertices $(j_1,j_2,\ldots,j_K)$ and $(k_1,k_2,\ldots,k_K)$ are connected by an edge if for all $1\le i\le K$, $j_i$ and $k_i$ are connected by an edge in $G_i$.
Define the distance between two vertices in $G$ that lie in the same connected component to be the minimum number of edges along a path from one vertex to the other. Compute the sum of the distances between vertex $(1,1,\ldots,1)$ and every vertex in the same component as it in $G$, modulo $10^9+7$.
Each graph description starts with $N_i$ and $M_i$ on a single line, followed by $M_i$ edges.
Consecutive graphs are separated by newlines for readability. It is guaranteed that $\sum N_i\le 10^5$ and $\sum M_i\le 2\cdot 10^5$.
2 2 1 1 2 4 4 1 2 2 3 3 4 4 1
4
$G$ contains $2\cdot 4=8$ vertices, $4$ of which are not connected to vertex $(1,1)$. There are $2$ vertices that are distance $1$ away from $(1,1)$ and $1$ that is distance $2$ away. So the answer is $2\cdot 1+1\cdot 2=4$.
3 4 4 1 2 2 3 3 1 3 4 6 5 1 2 2 3 3 4 4 5 5 6 7 7 1 2 2 3 3 4 4 5 5 6 6 7 7 1
706
$G$ contains $4\cdot 6\cdot 7=168$ vertices, all of which are connected to vertex $(1,1,1)$. The number of vertices that are distance $i$ away from $(1,1,1)$ for each $i\in [1,7]$ is given by the $i$-th element of the following array: $[4,23,28,36,40,24,12]$.