Public Judge

pjudge

Time Limit: 2 s Memory Limit: 512 MB Total points: 100

#21704. 【NOIP Round #4】拓扑序计数

Statistics

题目描述

本题中涉及到的图论定义:

  • 一个 $n$ 个点,点的编号为 $1,2,\dots,n$ 的有向图 $G=(V,E)$ 的拓扑序是一个 $1,2,\dots,n$ 的排列 $p$,且若 $E$ 中存在 $x\to y$ 的边,就有 $p$ 中 $x$ 出现在 $y$ 之前。

今天,算法竞赛机器人小 G 学习了拓扑排序相关知识。凭着强大的机器学习本领,它很快便一并学会了如何计算一个有向无环图的拓扑序个数。接着,它开始思考一个拓展问题:给定一个有向无环图 $G$ 和两个 $G$ 中的点 $u,v$,请你求出有多少种 $G$ 的拓扑序满足 $u$ 排在 $v$ 之前。

你知道稍加思考后小 G 也能秒掉这题。不巧,就在这时停电了,依靠插头进食的小 G 也因此停止工作了。所以你只好自己解决这个拓展问题了。

为了让问题更富有挑战性,设 $G$ 中总点数为 $n$,请你对所有 $n(n-1)$ 对 $(u,v)$ 都求出答案。

输入格式

本题有多组数据,第一行是数据组数 $T$。

对于每组数据:第一行两个正整数 $n,m$,分别为 $G$ 的点数和边数。接下来 $m$ 行,每行两个正整数 $x,y$,表示有向图里一条 $x\to y$ 的边。保证没有重边且 $x\lt y$(也就是 $[1,2,\dots,n]$ 总是一个合法拓扑序)。

保证同一个测试点中至多有 $5$ 组数据满足 $n>10$。

输出格式

对每组数据输出一个 $n\times n$ 的矩阵,第 $i$ 行第 $j$ 列是 $v=i,u=j$ 时的答案,注意 $(v,u)$ 的顺序和 $(i,j)$ 是反的。特别地,当 $i=j$ 时请你输出 0。

样例输入输出

样例输入 1

2
3 2
1 2
1 3
4 2
1 2
3 4

样例输出 1

0 0 0
2 0 1
2 1 0
0 0 3 1
6 0 5 3
3 1 0 0
5 3 6 0

样例 1 解释

对于第一组数据,原图共有两种拓扑序 $[1,2,3],[1,3,2]$。满足 $1$ 在 $2$ 前面的有 $2$ 种,所以答案矩阵的第 $2$ 行第 $1$ 列是 $2$;满足 $3$ 在 $2$ 前面的有 $1$ 种,所以答案矩阵的第 $2$ 行第 $3$ 列是 $1$。

样例 2/3

见下发文件。

样例 $2$ 满足子任务 $1$ 的限制。

样例 $3$ 满足子任务 $10$ 的限制。

数据范围

对于所有数据:$1\le T\le 100,1\le n\le 20,0\le m\le \binom n2$,保证同一个测试点中至多有 $5$ 组数据满足 $n>10$。

子任务编号 $n\le $ $m\le $ $T\le $ 分数
$1$ $5$ $\binom n2$ $20$ $10$
$2$ $20$ $0$ $5$
$3$ $1$ $5$
$4$ $2$ $5$
$5$ $10$ $10$
$6$ $10$ $\binom n2$ $30$ $5$
$7$ $12$ $40$ $5$
$8$ $14$ $50$ $10$
$9$ $16$ $60$ $5$
$10$ $17$ $70$ $5$
$11$ $18$ $80$ $10$
$12$ $19$ $90$ $5$
$13$ $20$ $100$ $20$

时间限制:$2\texttt{s}$

空间限制:$512\texttt{MB}$