← 返回题目列表

AtCoder · xmascon23_c

C. 夹子 夹子 夹子

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

配点 : 100 点

蟹 (N-1)“蟹 (N-2)“……“蟹 1“蟹 0「a_0」」」……」」

問題文

N 设为正整数。(0, 1, \ldots, 2N) 的重新排列 (a_0, a_1, \ldots, a_{2N}) ,满足所有 i = 0, 1, \ldots, N-1 反对 a_{2i+1} < a_{2i+2} 的整体集合为 A 。

a = (a_0, a_1, \ldots, a_{2N}) \in A , 定义f(a) 定义如下:

  • b_0 = a_0 。 删除
  • i = 0, 1, \ldots, N-1 , 定义b_{i+1} = \min\{\max\{b_i, a_{2i+1}\}, a_{2i+2}\} 。 删除
  • f(a) = b_N 定为。

N 并且,Q 整数 给出了 Z_1, Z_2, \ldots, Z_Q 已给出。各 j = 1, 2, \ldots, Q , 定义f(a) = Z_j 变为 a \in A 的数量 我们将其表示为 998244353 求余数。 打印除以

制約

  • 1 \le N \le 10^7.
  • 1 \le Q \le 250\,000.
  • 0 \le Z_1 < Z_2 < \cdots < Z_Q \le 2N.

入力

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

N Q
Z_1 Z_2 \cdots Z_Q

出力

j = 1, 2, \ldots, Q 的顺序,f(a) = Z_j 变为 a \in A 的数量 我们将其表示为 998244353 除以时的余数,以空格分隔输出。


入力例 1

2 5
0 1 2 3 4

出力例 1

0 3 24 3 0
  • a = (2, 3, 4, 0, 1), (3, 2, 4, 0, 1), (4, 2, 3, 0, 1) 什么时候 f(a) = 1 。
  • a = (0, 1, 2, 3, 4), (1, 0, 2, 3, 4), (2, 0, 1, 3, 4) 什么时候 f(a) = 3 。
  • 其他 a \in A 对于 f(a) = 2 。

入力例 2

3 7
0 1 2 3 4 5 6

出力例 2

0 30 96 378 96 30 0

入力例 3

4 9
0 1 2 3 4 5 6 7 8

出力例 3

0 630 1800 3870 10080 3870 1800 630 0

入力例 4

7 6
1 2 3 5 8 13

出力例 4

97297200 239500800 441579600 78828847 496821247 97297200