← 返回题目列表

AtCoder · mujin_pc_2018_g

G. 移动

中文机器翻译题面 查看原题

配点 : 800 点

問題文

在这个问题中 有了计算量 Q 查询。 在查询i 第二个查询是 由 7 整数 a_i,b_i,c_i,d_i,e_i,f_i,k_i 代表。 对于每个查询, 请将以下问题的答案输出为x_1=a_i,y_1=b_i,x_2=c_i,y_2=d_i,x_3=e_i,y_3=f_i,K=k_i 。

机器人 1 可用车辆、时间 0 有 直到 xy 平面上的点 我在 (0,0) 。 两个机器人 (0,0) 但是哪个 2 两个方向既不完全相同也不完全相反。 3 矢量 (x_1,y_1),(x_2,y_2),(x_3,y_3) 并根据以下规则移动。 机器人的坐标位于

  • 時刻 t 机器人所在坐标 (x,y) 然后时间 t+1 机器人有坐标 您属于 (x,y),(x+x_1,y+y_1),(x+x_2,y+y_2),(x+x_3,y+y_3) 之一。 给出了

非負整数 K 。时间 让我们计算 K 处有机器人的可能点的数量。 对于 998244353 后求余数。

制約

  • 1 \leq Q \leq 10^4
  • 0 \leq |a_i|,|b_i|,|c_i|,|d_i|,|e_i|,|f_i| \leq 10^9
  • 0 \leq k_i \leq 10^9
  • 各 i , 您可以获得(a_i,b_i),(c_i,d_i),(e_i,f_i) 都是 (0,0) 其中哪些 2 他们并不总是面向同一个方向; 2 他们没有面向完全相反的方向。更准确地说,哪个 2 的叉积 不是 0 不是
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

Q
a_1 b_1 c_1 d_1 e_1 f_1 k_1
:
a_Q b_Q c_Q d_Q e_Q f_Q k_Q

出力

对于每个查询,时间 打印除以 K 处有机器人的可能点的数量。 对于 998244353 后的余数。


入力例 1

9
1 0 0 1 1 1 3
1 0 0 1 -1 -1 3
3 1 4 1 5 9 265
77162 -78112 -90809 -88927 99617 -89012 1000000000
123 456 789 -123 -456 -789 987654321
0 1 2 3 4 5 0
10000000 10000000 20000000 30000000 -50000000 -80000000 130000000
123456789 442514372 -902777152 -78816277 -887267123 667261667 908855261
1 2 3 4 5 6 7

出力例 1

16
19
981646
677426955
667519055
1
233035917
508252191
64

在第一个查询中,时间 3 处有机器人的可能点是 该点表示为 (x,y)(0\leq x,y\leq 3) ,即 有 16 件。 2 个查询使用时间 3 处有机器人的可能点是 该点表示为 (-3,-3),(-2,-2),(-2,-1),(-1,-2),(-1,-1),(-1,0),(-1,1),(0,-1),(0,0),(0,1),(0,2),(0,3),(1,-1),(1,0),(1,1),(1,2),(2,0),(2,1),(3,0) 可以得到第 19 件。