题目详情题解（0）讨论（0）提交记录（0）

AT_abc265_e.[ABC265E] Warp

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

高桥君位于二维平面上的原点。
接下来，高桥君将进行 NN 次“跃迁”。每次跃迁时，他可以选择以下三种方式中的一种：

  • 从当前位置 (x,y)(x, y) 跃迁到 (x+A,y+B)(x+A, y+B)；
  • 从当前位置 (x,y)(x, y) 跃迁到 (x+C,y+D)(x+C, y+D)；
  • 从当前位置 (x,y)(x, y) 跃迁到 (x+E,y+F)(x+E, y+F)。

平面上有 MM 个障碍物，分别位于 (X1,Y1),…,(XM,YM)(X_1, Y_1),\ldots,(X_M, Y_M)，不能跃迁到这些坐标。

请问，经过 NN 次跃迁后，所有可能的移动路径有多少种？请将答案对 998244353998244353 取模后输出。

输入格式

输入通过标准输入给出，格式如下：

NN MM AA BB CC DD EE FF
X1X_1 Y1Y_1
X2X_2 Y2Y_2
⋮\vdots
XMX_M YMY_M

输出格式

请输出答案。

输入输出样例

  • 输入#1

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

    输出#1

    5

  • 输入#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

说明/提示

限制条件

  • 1≤N≤3001 \leq N \leq 300
  • 0≤M≤1050 \leq M \leq 10^5
  • −109≤A,B,C,D,E,F≤109-10^9 \leq A, B, C, D, E, F \leq 10^9
  • (A,B),(C,D),(E,F)(A, B), (C, D), (E, F) 两两不同
  • −109≤Xi,Yi≤109-10^9 \leq X_i, Y_i \leq 10^9
  • (Xi,Yi)≠(0,0)(X_i, Y_i) \neq (0, 0)
  • (Xi,Yi)(X_i, Y_i) 两两不同
  • 输入中的所有数均为整数

样例解释 1

共有以下 55 种路径：

  • (0,0)→(1,1)→(2,3)(0,0)\to(1,1)\to(2,3)
  • (0,0)→(1,1)→(2,4)(0,0)\to(1,1)\to(2,4)
  • (0,0)→(1,3)→(2,4)(0,0)\to(1,3)\to(2,4)
  • (0,0)→(1,3)→(2,5)(0,0)\to(1,3)\to(2,5)
  • (0,0)→(1,3)→(2,6)(0,0)\to(1,3)\to(2,6)

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页