E - Warp

Contest Duration: 2022-08-21(Sun) 12:00 - 2022-08-21(Sun) 13:40 (local time) (100 minutes) Back to Home

E - Warp Editorial

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : $500$ 点

問題文

$2$ 次元平面の原点に高橋君がいます。
高橋君はこれから、ワープを $N$ 回繰り返します。各ワープでは、以下の $3$ つのうちいずれか $1$ つを行います。

現在いる座標 $(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$

出力

答えを出力せよ。

入力例 1Copy

Copy

2 2
1 1 1 2 1 3
1 2
2 2

出力例 1Copy

Copy

以下の $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)$

入力例 2Copy

Copy

10 3
-1000000000 -1000000000 1000000000 1000000000 -1000000000 1000000000
-1000000000 -1000000000
1000000000 1000000000
-1000000000 1000000000

出力例 2Copy

Copy

入力例 3Copy

Copy

300 0
0 0 1 0 0 1

出力例 3Copy

Copy

292172978

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 1Copy

Copy

2 2
1 1 1 2 1 3
1 2
2 2

Sample Output 1Copy

Copy

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 2Copy

Copy

10 3
-1000000000 -1000000000 1000000000 1000000000 -1000000000 1000000000
-1000000000 -1000000000
1000000000 1000000000
-1000000000 1000000000

Sample Output 2Copy

Copy

Sample Input 3Copy

Copy

300 0
0 0 1 0 0 1

Sample Output 3Copy

Copy

292172978