QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 1024 MB Total points: 100
统计

小 K 有一张含有 $n$ 个点的竞赛图。点的编号依次为 $1\sim n$。众所周知,竞赛图是一张有向图,满足 $\forall 1\le i < j \le n$,有向边 $i\to j$ 和 $j\to i$ 中恰好存在一条边。

小 K 在学习网络课程,这个课程的其中一项作业是将这个竞赛图传输到另外一台计算机上。但是传输时可能遇到了信号干扰,导致传输到新的计算机上的时候会有恰好 $1$ 条边的方向被反转。小 K 快速地解决了这个问题。但是小 K 很好奇,对于这一张给定的竞赛图,$\forall 1 \le i < j \le n$,如果连接 $i, j$ 的边方向被反转了,这一张新的竞赛图有多少个极大强连通分量。

输入格式

第一行一个数 $T$($1 \le T \le 10\,000$)表示数据组数。

对于每组数据:

第一行一个数 $n$($1 \le n \le 5000$)表示节点数。

接下来 $n-1$ 行,第 $i$ 行为一个长度为 $\left\lceil\frac i4\right\rceil$ 的字符串,其中第 $j$ 个字符为 $\sum_{k=0}^3 2^k E_{i+1, 4j+k-3}$ 对应的 $16$ 进制数(即 $10\sim 15$ 对应大写字母 $\texttt A \sim \texttt F$),其中 $E_{i,j}=1$ 当且仅当 $j < i$ 且 $i, j$ 之间的边的方向是从 $i$ 指向 $j$。

保证至多只有一组数据 $n > 10$。

输出格式

对于每组数据,输出一行一个数,即 $\sum_{i=1}^n \sum_{j=1}^{i-1} 2^{(i-2)(i-1)/2+j-1} ans_{i,j}$ 对 $10^9+7$ 取模的值,其中 $ans_{i,j}$ 表示 $i,j$ 之间的边翻转之后得到的竞赛图的极大强连通分量个数。

样例数据

样例输入

2
3
0
2
6
1
3
7
F
F1

样例输出

19
153406

样例解释

样例的第一组数据有 $3$ 个点,边集为 $\{(1, 2), (1, 3), (3, 2)\}$,$ans_{1,2} = 1$,$ans_{1,3} = ans_{2,3} = 3$。

数据范围

对于全部数据,$T \le 10\,000$,$1 \le n \le 5000$。

子任务 1($20\%$):$n \le 100$;

子任务 2($20\%$):$n \le 300$;

子任务 3($20\%$):$n \le 500$;

子任务 4($20\%$):$n \le 1500$;

子任务 5($20\%$):$n \le 5000$。