103097: [Atcoder]ABC309 Ex - Simple Path Counting Problem
Description
Score : $650$ points
Problem Statement
We have a grid with $N$ rows and $M$ columns. We denote by $(i,j)$ the cell in the $i$-th row from the top and $j$-th column from the left.
You are given integer sequences $A=(A_1,A_2,\dots,A_K)$ and $B=(B_1,B_2,\dots,B_L)$ of lengths $K$ and $L$, respectively.
Find the sum, modulo $998244353$, of the answers to the following question over all integer pairs $(i,j)$ such that $1 \le i \le K$ and $1 \le j \le L$.
- A piece is initially placed at $(1,A_i)$. How many paths are there to take it to $(N,B_j)$ by repeating the following move $(N-1)$ times?
- Let $(p,q)$ be the piece's current cell. Move it to $(p+1,q-1),(p+1,q)$, or $(p+1,q+1)$, without moving it outside the grid.
Constraints
- $1 \le N \le 10^9$
- $1 \le M,K,L \le 10^5$
- $1 \le A_i,B_j \le M$
Input
The input is given from Standard Input in the following format:
$N$ $M$ $K$ $L$ $A_1$ $A_2$ $\dots$ $A_K$ $B_1$ $B_2$ $\dots$ $B_L$
Output
Print the answer.
Sample Input 1
3 4 1 2 1 1 2
Sample Output 1
4
For $(i,j)=(1,1)$, the following two paths are possible:
- $(1,1) \rightarrow (2,1) \rightarrow (3,1)$
- $(1,1) \rightarrow (2,2) \rightarrow (3,1)$
For $(i,j)=(1,2)$, the following two paths are possible:
- $(1,1) \rightarrow (2,1) \rightarrow (3,2)$
- $(1,1) \rightarrow (2,2) \rightarrow (3,2)$
Thus, the answer is $2 + 2 =4$.
Sample Input 2
5 8 4 5 3 1 4 1 2 7 1 8 2
Sample Output 2
137
Sample Input 3
883671387 87719 10 12 86879 64174 47274 41688 17713 50897 53989 7210 30894 5714 60358 28835 48036 48450 67149 36558 35929 69025 77539 19195 60762 60721
Sample Output 3
941873621
Input
Output
问题描述
我们有一个有 N 行 M 列的网格。我们用 $(i,j)$ 表示从上数第 i 行、从左数第 j 列的单元格。
给你长度分别为 K 和 L 的整数序列 $A=(A_1,A_2,\dots,A_K)$ 和 $B=(B_1,B_2,\dots,B_L)$。
对于所有的整数对 $(i,j)$,使得 $1 \le i \le K$ 和 $1 \le j \le L$,找出以下问题答案的和(模 $998244353$):
- 一块棋子最初放在 $(1,A_i)$。有多少种路径可以将它移到 $(N,B_j)$,通过重复以下移动 $(N-1)$ 次?
- 让 $(p,q)$ 是棋子当前所在的单元格。将它移到 $(p+1,q-1),(p+1,q)$ 或 $(p+1,q+1)$,不要让它移到网格之外。
约束
- $1 \le N \le 10^9$
- $1 \le M,K,L \le 10^5$
- $1 \le A_i,B_j \le M$
输入
输入数据从标准输入以以下格式给出:
$N$ $M$ $K$ $L$ $A_1$ $A_2$ $\dots$ $A_K$ $B_1$ $B_2$ $\dots$ $B_L$
输出
打印答案。
样例输入 1
3 4 1 2 1 1 2
样例输出 1
4
对于 $(i,j)=(1,1)$,有以下两种可能的路径:
- $(1,1) \rightarrow (2,1) \rightarrow (3,1)$
- $(1,1) \rightarrow (2,2) \rightarrow (3,1)$
对于 $(i,j)=(1,2)$,有以下两种可能的路径:
- $(1,1) \rightarrow (2,1) \rightarrow (3,2)$
- $(1,1) \rightarrow (2,2) \rightarrow (3,2)$
因此,答案为 $2 + 2 =4$。
样例输入 2
5 8 4 5 3 1 4 1 2 7 1 8 2
样例输出 2
137
样例输入 3
883671387 87719 10 12 86879 64174 47274 41688 17713 50897 53989 7210 30894 5714 60358 28835 48036 48450 67149 36558 35929 69025 77539 19195 60762 60721
样例输出 3
941873621