QOJ.ac

QOJ

Time Limit: 9 s Memory Limit: 1024 MB Total points: 100
统计

有一个 $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_{i}F_{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_{i}F_{j} \bmod p$ 的结果。

样例组

样例 1 输入

1 3 3 998244353
3 1 2 
3 2 2 
3 2 3 1 
1 3 2 
1 2 1 1 
1 1 1 1

样例 1 输出

559

样例 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 输入

1 10 8 998244353
1 1 223419641 557071951 121 92666830 0 49321567 
813349214 695956508 278 0 231694534 0 0 295169358 669776412 451 
139 0 448 354283551 0 293318815 525972283 769691152 124 
389028745 248 122590563 0 99 618248111 561941070 0 
575275733 93848250 0 390 437 0 694493030 90 0 222 0 
142 0 802726546 415295998 155953578 814571694 373754122 127 0

样例 2 输出

460779351

样例 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 $5\,000$ $5\,000$ $ $ $ $ $ $ $ $ $ $ $ $
2 5 $2 \times 10^5$ $2 \times 10^5$ $=0$ $=1$ $=0$
3 8 $ $ $=0$
4 8 $=0$ $ $
5 5 $ $
6 15 $ $ $=[i=m]$
7 16 $20\,000$ $ $
8 16 $2 \times 10^5$ 有且仅有一个位置非 $0$
9 9 $ $
10 15 $10^5$ $10^5$