実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 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 個です。