P12475 [集训队互测 2024] 路径计数

由于评测机性能差距，本题时限增加了 3 秒。

有一个 $n$ 行 $m$ 列的网格，网格上共有 $(n + 1) \times (m + 1)$ 个格点，其中第 $x$ 行第 $y$ 列的格点用一个二元组 $(x, y)$ 表示(格点的行与列均从 0 开始编号)。 初始时网格没有边，现在依次加入 $(3m + 1)n$ 条有向边： 1. 对于 $0 \leq i \leq n - 1, 0 \leq j \leq m - 1$ 加入 $A_j$ 条本质不同的从 $(i, j)$ 到 $(i + 1, j + 1)$ 的有向边。 2. 对于 $0 \leq i \leq n - 1, 0 \leq j \leq m$ 加入 $B_i + C_j$ 条本质不同的从 $(i, j)$ 到 $(i + 1, j)$ 的有向边。 3. 对于 $0 \leq i \leq n - 1, 1 \leq j \leq m$ 加入 $D_j$ 条本质不同的从 $(i, j)$ 到 $(i + 1, j - 1)$ 的有向边。 现在令对于满足 $0 \leq x \leq n, 0 \leq y \leq m$ 的整数 $x, y$，定义 $W(x, y)$ 表示 $(0, 0)$ 到 $(x, y)$ 有多少条本质不同的路径，不难证明路径的个数是有限的。现在你要求出 $\sum_{i=0}^{n} \sum_{j=0}^{m} W(i, j)E_iF_j \bmod p$ 的结果。

第一行输入三个正整数 $c, n, m, p$，第一个数表示子任务编号(特别的，样例中的 $c$ 表示该样例的满足的限制与第 $c$ 个子任务所满足的限制相同)，第二个数与第三个数描述网格的大小，第四个数表示答案需要取模的模数。 第二行输入 $m$ 个数，其中第 $i$ 个数表示 $A_{i-1}$ 的取值。 第三行输入 $n$ 个数，其中第 $i$ 个数表示 $B_{i-1}$ 的取值。 第四行输入 $m + 1$ 个数，其中第 $i$ 个数表示 $C_{i-1}$ 的取值。 第五行输入 $m$ 个数，其中第 $i$ 个数表示 $D_i$ 的取值。 第六行输入 $n + 1$ 个数，其中第 $i$ 个数表示 $E_{i-1}$ 的取值。 最后一行输入 $m + 1$ 个数，其中第 $i$ 个数表示 $F_{i-1}$ 的取值。

输出一行一个整数表示 $\sum_{i=0}^{n} \sum_{j=0}^{m} W(i, j)E_iF_j \bmod p$ 的结果。

### 样例 1 解释 $W(0,0) = 1, W(1,0) = 6, W(1,1) = 3, W(2,0) = 33, W(2,1) = 30, W(2,2) = 3, W(3,0) = 195, W(3,1) = 228, W(3,2) = 45, W(3,3) = 6$，其余位置 $W$ 均为 $0$，不难得到答案为 $559$。 ### 样例 2 解释 经过运算可以得到答案为 $460779351$，注意要对 $998244353$ 取模。 ### 样例 3~12 对于下发样例 $i$，其满足子任务 $i - 2$ 的所有限制。 ### 子任务 对于所有数据，保证 $1 \leq n, m \leq 2 \times 10^5$，$1 \leq p \leq 10^9$，$0 \leq A_i, B_i, C_i, D_i, E_i, F_i < p$，不保证 $p$ 为质数，但对于 $p \neq 998244353$ 的数据满足 $1 \leq n, m \leq 10^5$。 | 子任务编号 | 子任务分值 | $n \leq$ | $m \leq$ | $A_i$ | $B_i$ | $C_i$ | $D_i$ | $E_i$ | $F_i$ | $p = 998244353$ | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | 1 | 3 | 5000 | 5000 | - | - | - | - | - | - | 是 | | 2 | 5 | $2 \times 10^5$ | $2 \times 10^5$ | - | $= 0$ | $= 1$ | $= 0$ | - | - | 是 | | 3 | 8 | $2 \times 10^5$ | $2 \times 10^5$ | - | - | $= 0$ | $= 0$ | - | - | 是 | | 4 | 8 | $2 \times 10^5$ | $2 \times 10^5$ | - | $= 0$ | - | $= 0$ | - | - | 是 | | 5 | 5 | $2 \times 10^5$ | $2 \times 10^5$ | - | - | - | - | $= 0$ | - | 是 | | 6 | 15 | $2 \times 10^5$ | $2 \times 10^5$ | - | - | - | - | - | $= [i = m]$ | 是 | | 7 | 16 | $2 \times 10^5$ | 20000 | - | - | - | - | - | - | 是 | | 8 | 16 | $2 \times 10^5$ | $2 \times 10^5$ | - | - | - | - | - | 有且仅有一个位置非 0 | 是 | | 9 | 9 | $2 \times 10^5$ | $2 \times 10^5$ | - | - | - | - | - | - | 是 | | 10 | 15 | $10^5$ | $10^5$ | - | - | - | - | - | - | 否 | 表格中的 - 表示无特殊性质。