有一个 n 行 m 列的网格,网格上共有 (n+1)×(m+1) 个格点,其中第 x 行第 y 列的格点用一个二元组 (x,y) 表示(格点的行与列均从 0 开始编号)。
初始时网格没有边,现在依次加入 (3m+1)n 条有向边:
- 对于 0≤i≤n−1,0≤j≤m−1 加入 Aj 条本质不同的从 (i,j) 到 (i+1,j+1) 的有向边。
- 对于 0≤i≤n−1,0≤j≤m 加入 Bi+Cj 条本质不同的从 (i,j) 到 (i+1,j) 的有向边。
- 对于 0≤i≤n−1,1≤j≤m 加入 Dj 条本质不同的从 (i,j) 到 (i+1,j−1) 的有向边。
现在令对于满足 0≤x≤n,0≤y≤m 的整数 x,y,定义 W(x,y) 表示 (0,0) 到 (x,y) 有多少条本质不同的路径,不难证明路径的个数是有限的。现在你需要求出 ∑ni=0∑mj=0W(i,j)EiFjmodp 的结果。
输入格式
第一行输入三个正整数 c,n,m,p,第一个数表示子任务编号(特别的,样例中的 c 表示该样例的满足的限制与第 c 个子任务所满足的限制相同),第二个数与第三个数描述网格的大小,第四个数表示答案需要取模的模数。
第二行输入 m 个数,其中第 i 个数表示 Ai−1 的取值。
第三行输入 n 个数,其中第 i 个数表示 Bi−1 的取值。
第四行输入 m+1 个数,其中第 i 个数表示 Ci−1 的取值。
第五行输入 m 个数,其中第 i 个数表示 Di 的取值。
第六行输入 n+1 个数,其中第 i 个数表示 Ei−1 的取值。
最后一行输入 m+1 个数,其中第 i 个数表示 Fi−1 的取值。
输出格式
输出一行一个整数表示 ∑ni=0∑mj=0W(i,j)EiFjmodp 的结果。
样例组
样例 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≤n,m≤2×105,1≤p≤109,0≤Ai,Bi,Ci,Di,Ei,Fi<p,不保证 p 为质数,但对于 p≠998244353 的数据满足 1≤n,m≤105。
子任务编号 | 子任务分值 | n≤ | m≤ | Ai | Bi | Ci | Di | Ei | Fi | p=998244353 |
---|---|---|---|---|---|---|---|---|---|---|
1 | 3 | 5000 | 5000 | 是 | ||||||
2 | 5 | 2×105 | 2×105 | =0 | =1 | =0 | ||||
3 | 8 | =0 | ||||||||
4 | 8 | =0 | ||||||||
5 | 5 | |||||||||
6 | 15 | =[i=m] | ||||||||
7 | 16 | 20000 | ||||||||
8 | 16 | 2×105 | 有且仅有一个位置非 0 | |||||||
9 | 9 | |||||||||
10 | 15 | 105 | 105 | 否 |