k 维空间路径问题(K-Dimensional Lattice Paths)

题目描述

我们都知道二维空间路径数问题。即从 $(1,1)$ 走到 $(n,m)$，每次可以往两个维度的任意维度前进一步，即从 $(x,y)$ 走到 $(x+1,y)$ 或者 $(x,y+1)$，问路径数量。

现在，有一个 $k$ 维空间，刚开始小 Z 在 $(0,0,\cdots,0)$ 点，终点位于 $(s_1,s_2,\cdots,s_k)$ 点。小 Z 每一步可以在任意维度上前进一步，具体地，假设小 Z 现在在 $(x_1, x_2,...,x_k)$，那么下一步小 Z 可以走到 $(x_1+1,x_2,...,x_k),(x_1,x_2+1,...,x_k),...,(x_1,x_2,\cdots,x_k+1)$ 这 $k$ 个点中的任意一个。

但是，在这 $k$ 维空间中，又有 $n$ 个点是障碍物，这些点不能走，这 $n$ 个点的坐标分别为 $(a_{11}, a_{12},...a_{1k}),(a_{21}, a_{22},...a_{2k}),...,(a_{n1}, a_{n2},...a_{nk})$。

问小 Z 有多少种不同的方案，可以在不经过 $n$ 个障碍物点的情况下到达终点，答案可能很大，只需要输出对 $998244353$ 取模的结果。

输入格式

第一行包含两个正整数 $k,\ n$，空间维度和障碍物点数。

第二行包含 $k$ 个整数，$s_1,s_2,...,s_k$ ，表示终点的坐标。

接下来 $n$ 行，每行包含 $k$ 个整数，$a_{i1}, a_{i2},...,a_{ik}$ ，表示第 $i$ 个障碍物点的坐标。

输出格式

输出一行正整数表示方案数，对 $998244353$ 取模。

样例输入 #1

2 0
2 1

样例输出 #1

3

样例输入 #2

2 1
2 2
1 1

样例输出 #2

2

样例输入 #3

3 2
2 2 1
0 0 1
1 2 1

样例输出 #3

15

数据范围

【样例 1 解释】

三条路径分别为 $(0,0)\rightarrow(0,1)\rightarrow(1,1)\rightarrow(2,1)$ ，$(0,0)\rightarrow(1,0)\rightarrow(1,1)\rightarrow(2,1)$ ， $(0,0)\rightarrow(1,0)\rightarrow(2,0)\rightarrow(2,1)$ 。

【样例 2 解释】

两条路径分别为 $(0,0)\rightarrow(0,1)\rightarrow(0,2)\rightarrow(1,2)\rightarrow(2,2)$ ， $(0,0)\rightarrow(1,0)\rightarrow(2,0)\rightarrow(2,1)\rightarrow(2,2)$ 。

【数据范围】

设 $m = max(s_1, s_2,...,s_k)$ 。

对于前 $10\%$ 的数据，满足 $k = 2,\ n = 0,\ m\le5000$ 。

对于前 $30\%$ 的数据，满足 $k = 2,\ m\le5000$ 。

对于另 $20\%$ 的数据，满足 $k = 2,\ n = 0$ 。

对于另 $20\%$ 的数据，满足 $k = 2$ 。

对于另 $10\%$ 的数据，满足 $k = 3,\ n = 0$。

对于 $100\%$ 的数据，满足 $2\le k\le10,\ 0\le n\le5000,\ 1\le m\le10^5,\ 0\le a_{ik}\le s_{ik}$ ，保证 $n$ 个点以及起点和终点都互不相同 。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1900。

测试点分布

出处：原题链接