#1749. 基础图论练习题

    ID: 1749 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1090来源:qoj.ac数据:公开样例强连通分量枚举

基础图论练习题

基础图论练习题

题目描述

标题: 基础图论练习题 - Problem - QOJ.ac

#5407. 基础图论练习题

Statistics

The problem was used in the following contests:

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

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

输入格式

第一行一个数 T(1≤T≤10000)表示数据组数。

对于每组数据:

第一行一个数 n(1≤n≤5000)表示节点数。

接下来 n−1 行,第 i 行为一个长度为 ⌈i4⌉ 的字符串,其中第 j 个字符为 ∑k=032kEi+1,4j+k−3 对应的 16 进制数(即 10∼15 对应大写字母 A∼F),其中 Ei,j=1 当且仅当 j<i 且 i,j 之间的边的方向是从 i 指向 j。

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

输出格式

对于每组数据,输出一行一个数,即 ∑i=1n∑j=1i−12(i−2)(i−1)/2+j−1ansi,j 对 109+7 取模的值,其中 ansi,j 表示 i,j 之间的边翻转之后得到的竞赛图的极大强连通分量个数。

样例数据

样例输入

2
3
0
2
6
1
3
7
F
F1

样例输出

19
153406

样例解释

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

数据范围

对于全部数据,T≤10000,1≤n≤5000。

子任务 1(20%):n≤100;

子任务 2(20%):n≤300;

子任务 3(20%):n≤500;

子任务 4(20%):n≤1500;

子任务 5(20%):n≤5000。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

2
3
0
2
6
1
3
7
F
F1
19
153406