给定一个包含 n 个点的有向无环图,每条边的边权值为 0 或 1 。
现在有一个空向量 V ,假设从节点 1 开始进行以下dfs操作:
// 从节点 i 为开始进行 dfs
void dfs(int i) {
// 遍历节点 i 的每条出边
for(int j = 1; j <= S[i]; j++) {
V.push_back(B[i][j]); // 将当前边边 B[i][j] 加入向量 V 的末尾
dfs(A[i][j]); // dfs递归后继节点A[i][j]
}
}
在上述dfs操作结束后,向量 V 内会添加许多元素,求向量 V 的逆序数对数。
由于向量 V 可能包含很多元素,导致逆序数对数十分多,因此只需输出答案对 998244353 取模结果即可。
逆序对的定义请参考 https://baike.baidu.com/item/逆序对