3599. [NOI 2021]路径交点

【题目描述】

小L有一个有向图，图中的顶点可以分为$k$层，第$i$层有$n_i$个顶点，第$1$层与第$k$层顶点数相同，即$n_1=n_k$，且对于第$j$（$2 \leq j \leq k-1$）层，$n_1 \leq n_j \leq {2n}_1$。对于第$j$（$1 \leq j < k$），以它们为起点的边只会连向第$j + 1$层的顶点。没有边连向第$1$层的顶点，第$k$层的顶点不会向其他顶点连边。

现在小L要从这个图中选出$n_1$条路径，每条路径以第1层顶点为起点，第k层顶点为终点，并要求图中的每个顶点至多出现在一条路径中。更具体地，把每一层顶点按照$1,2 \dots n_1$进行编号，则每条路径可以写成一个$k$元组（p_1,p_2 \dots p_k），表示这条路径依次经过第$j$层的$p_j$（$1 \leq p_j \leq n_j$）号顶点，并且第$j$($1 \leq j < k$)层的$p_j$号顶点有一条边连向第$j+1$层的第$p_{j+1}$号顶点。

小L把这些路径画在纸上，发现它们会产生若干个交点。对于两条路径$P,Q$,分别设它们在第$j$层与第$j+1$层之间的连边为（$P_j,P_{j+1}$）与（$Q_j,Q_{j+1}$），若

$$（P_j - Q_j）\times （P_{j+1} - Q_{j+1}） <  0$$

则称它们在第$j$层后产生了一个交点。两条路径的交点数为它们在第$1,2 \dots k-1$后产生的交点总数。对于整个路径方案，它的交点数为两两不同路径间交点数之和。例如下图是一个$3$条路径，共$3$个交点的例子，其中红色点是交点。

小 L 现在想知道有偶数个交点的路径方案数比有奇数个交点的路径方案数多多少个。两个路径方案被视为相同的，当且仅当它们的$n_1$条路径按第一层起点编号顺序写下的$k$元组能对应相同。由于最后的结果可能很大，请你输出它对$998244353$（一个大质数）取模后的值。

【输入格式】

本题有多组数据，输入数据第一行一个正整数$T$，表示数据组数。对于每组数据：

第一行一个正整数 $k$，表示一共有$k$层顶点。

第二行包含$k$个整数$n_1,n_2 \dots n_k$，依次表示每一层的顶点数量。保证$n_1 = n_k$,且$n_1 \leq n_i \leq {2n}_1$（$2 \leq i \leq k-1$）

第三行包含$k-1$个整数$m_1,m_2,\dots m_{k-1}$，依次表示第$j$层顶点到第$j+1$层顶点的边数。保证$m_j \leq n_j \times n_{j+1}$

接下来有$k-1$段输入。第$j$（$1 \leq j < k$）段输入包含$m_j$行，每一行两个整数$u,v$，表示第$j$层的$u$号顶点有一条边连向第$j+1$层的$v$号顶点。

数据保证图中不会出现重边。

【输出格式】

输出共$T$行，每行一个整数，表示该组数据的答案对$998244353$取模后的值

【样例输入】

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

【样例输出】

1

【样例说明】

偶数个交点的方案有 2 个，奇数个交点的方案有 1 个，所以答案为 1。

将下表中路径 1 和路径 2 的方案交换，将会得到相同的方案，例如路径 1 为 (2, 3, 1) 且路径 22 为 (1, 1, 2) 的方案与方案 1 是相同的方案，所以不会被计入答案。

【其他测试样例】

其他测试样例下载

注意：样例2约束与7-8一致

    样例3约束与9-10一致

    样例4约束与14-15一致

【数据规模与约定】

对于所有的测试数据：$2 \leq k \leq 100$，$2 \leq n_1 \leq 100$，$1 \leq T \leq 5$。

每个测试点中，保证$n_1 > 10$的数据只有$1$组。

特殊性质A：对于所有$i$（$2 \leq k \leq k-1$），满足$n_i = n_1$

特殊性质B：保证路径方案总数至多为1

【题目来源】

NOI2021 Day1 Task2