← 返回题目列表

AtCoder · ajo2025_final_b

B. 插补

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

配点 : 800 点

問題文

小助君在生日时收到了 N 次整数係数多項式 f(x),g(x) 。 对此感到高兴的小助君,h(x)=2^x\times f(x) + g(x) 定义了,h(0),h(1),\cdots,h(2N+1) 的值用 \text{mod }{998244353} 进行了计算。 然后,h(i) \bmod 998244353=A_i 并记录下它是

有一天,小助君不小心弄丢了 f(x),g(x) 。 现在只剩下 A_0,A_1,\cdots,A_{2N+1} 的值了。 不过小助君很聪明,所以即使在否定这个问题的情况下(小助君知道连“自己”都是题面中的登场人物!),也能从这些值中求出 f(x),g(x) 的系数 \text{mod }{998244353} 发现可以唯一恢复。

A_0,A_1,\cdots,A_{2N+1} 以及 X 由于给出了,h(X) \bmod 998244353 请计算的值。

制約

  • 0 \leq N \leq 125000
  • 0 \leq X \leq 9 \times 10^8
  • 0 \leq A_i < 998244353
  • 所有输入均为整数

入力

输入将按照以下格式从标准输入给出。

N X
A_0 A_1 \ldots A_{2N+1}

出力

输出答案。


入力例 1

0 2
5 7

出力例 1

11

f(x)=2,g(x)=3 是。


入力例 2

1 5
3 9 24 61

出力例 2

359

f(x)=2x+1,g(x)=x+2 是。


入力例 3

3 0
785439575 250040585 709423541 945005786 19237225 404191279 250876592 22672563

出力例 3

785439575

入力例 4

10 12345678
519729086 344065186 273714212 560047125 139793596 542901248 520999410 855572558 498896932 418633758 742973826 248730678 238856535 319502970 908902333 164543594 245101681 197971506 714635866 966125570 768080799 80565655

出力例 4

57546937