配点 : 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 件。