102654: [AtCoder]ABC265 E - Warp
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Score : $500$ points
Problem Statement
Takahashi is at the origin of a two-dimensional plane.
Takahashi will repeat teleporting $N$ times. In each teleportation, he makes one of the following moves:
- Move from the current coordinates $(x,y)$ to $(x+A,y+B)$
- Move from the current coordinates $(x,y)$ to $(x+C,y+D)$
- Move from the current coordinates $(x,y)$ to $(x+E,y+F)$
There are obstacles on $M$ points $(X_1,Y_1),\ldots,(X_M,Y_M)$ on the plane; he cannot teleport to these coordinates.
How many paths are there resulting from the $N$ teleportations? Find the count modulo $998244353$.
Constraints
- $1 \leq N \leq 300$
- $0 \leq M \leq 10^5$
- $-10^9 \leq A,B,C,D,E,F \leq 10^9$
- $(A,B)$, $(C,D)$, and $(E,F)$ are distinct.
- $-10^9 \leq X_i,Y_i \leq 10^9$
- $(X_i,Y_i)\neq(0,0)$
- $(X_i,Y_i)$ are distinct.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$N$ $M$ $A$ $B$ $C$ $D$ $E$ $F$ $X_1$ $Y_1$ $X_2$ $Y_2$ $\vdots$ $X_M$ $Y_M$
Output
Print the answer.
Sample Input 1
2 2 1 1 1 2 1 3 1 2 2 2
Sample Output 1
5
The following $5$ paths are possible:
- $(0,0)\to(1,1)\to(2,3)$
- $(0,0)\to(1,1)\to(2,4)$
- $(0,0)\to(1,3)\to(2,4)$
- $(0,0)\to(1,3)\to(2,5)$
- $(0,0)\to(1,3)\to(2,6)$
Sample Input 2
10 3 -1000000000 -1000000000 1000000000 1000000000 -1000000000 1000000000 -1000000000 -1000000000 1000000000 1000000000 -1000000000 1000000000
Sample Output 2
0
Sample Input 3
300 0 0 0 1 0 0 1
Sample Output 3
292172978
Input
题意翻译
### 题目描述 ZK 现在在一个二维平面。他现在会进行 $N$ 次传送，每次传送回执行如下移动之一： - 从当前点 $(x,y)$ 移动到 $(x+A,y+B)$； - 从当前点 $(x,y)$ 移动到 $(x+C,y+D)$； - 从当前点 $(x,y)$ 移动到 $(x+E,y+F)$。 同时在这个平面上有 $M$ 个点 $(X_1,Y_1),\ldots,(X_M,Y_M)$ ，这些点 ZK 是无法停留或经过的。 问 $N$ 次传送一共会有多少种路径？输出答案对 $998244353$ 取模。 ### 输入描述 第一行两个整数 $N,M\;(1\le N \le 300, 0\le M \le 10^5)$。 第二行六个整数 $A,B,C,D,E,F\;(-10^9 \le A,B,C,D,E,F \le 10^9)$，保证无重复的二元对。 接下来 $M$ 行，每行两个整数 $X_i, Y_i\;(-10^9\le X_i,Y_i\le 10^9)$。保证 $(X_i,Y_i)\ne (0,0)$ 且无重复二元对。 ### 输出描述 输出一行一个数字代表答案。 ### 样例 1 解释 - $(0,0)\to(1,1)\to(2,3)$； - $(0,0)\to(1,1)\to(2,4)$； - $(0,0)\to(1,3)\to(2,4)$； - $(0,0)\to(1,3)\to(2,5)$； - $(0,0)\to(1,3)\to(2,6)$。Output
分数：500分
问题描述
高桥君位于二维平面上的原点处。
高桥君将重复进行$N$次瞬间移动。每次瞬间移动，他将做出以下一种动作：
- 从当前位置$(x,y)$移动到$(x+A,y+B)$
- 从当前位置$(x,y)$移动到$(x+C,y+D)$
- 从当前位置$(x,y)$移动到$(x+E,y+F)$
平面上有$M$个障碍点$(X_1,Y_1),\ldots,(X_M,Y_M)$；他不能瞬间移动到这些坐标。
通过$N$次瞬间移动可以形成多少种路径？找到结果对$998244353$取模后的数量。
限制条件
- $1 \leq N \leq 300$
- $0 \leq M \leq 10^5$
- $-10^9 \leq A,B,C,D,E,F \leq 10^9$
- $(A,B)$, $(C,D)$和$(E,F)$各不相同。
- $-10^9 \leq X_i,Y_i \leq 10^9$
- $(X_i,Y_i)\neq(0,0)$
- $(X_i,Y_i)$各不相同。
- 输入中的所有值都是整数。
输入
从标准输入以以下格式获取输入：
$N$ $M$ $A$ $B$ $C$ $D$ $E$ $F$ $X_1$ $Y_1$ $X_2$ $Y_2$ $\vdots$ $X_M$ $Y_M$
输出
打印答案。
样例输入1
2 2 1 1 1 2 1 3 1 2 2 2
样例输出1
5
可能的路径有以下$5$种：
- $(0,0)\to(1,1)\to(2,3)$
- $(0,0)\to(1,1)\to(2,4)$
- $(0,0)\to(1,3)\to(2,4)$
- $(0,0)\to(1,3)\to(2,5)$
- $(0,0)\to(1,3)\to(2,6)$
样例输入2
10 3 -1000000000 -1000000000 1000000000 1000000000 -1000000000 1000000000 -1000000000 -1000000000 1000000000 1000000000 -1000000000 1000000000
样例输出2
0
样例输入3
300 0 0 0 1 0 0 1
样例输出3
292172978