[AdditionalFile172.zip](file://AdditionalFile172.zip?type=additional_file)

#172. 多项式欧几里得

标签: 传统 | 时间限制: 6000 ms | 内存限制: 512 MiB 通过: 99 | 提交: 194

题目描述

这是一道模板题。

给你一个次数为 $n$ 且 $n$ 次项系数为 1 的多项式 $M(x)$ 和一个不超过 $n - 1$ 次的多项式 $P(x)$，求一个不超过 $n - 1$ 次的多项式 $Q(x)$，满足 $P(x)Q(x) \equiv 1 \pmod{M(x)}$。

保证 $M(x)$ 与 $P(x)$ 没有公因式。

其中系数在 $\mathbb{F}_p$ 下进行，其中 $p = 998244353$。

输入格式

第一行输入一个整数 $n$，表示多项式的次数。

接下来一行输入 $n + 1$ 个整数，从低到高次表示 $M(x)$ 的各项系数，保证最后一个数为 1。

接下来一行输入 $n$ 个整数，从低到高次表示 $P(x)$ 的各项系数。

输出格式

输出一行 $n$ 个整数，从低到高次表示 $Q(x)$ 的各项系数。

样例 1

输入

5
4 1 5 4 1 1
1 9 8 1 0

输出

287603356 114420498 32582651 248944523 227744016

样例 2

输入

5
4 1 5 4 1 1
287603356 114420498 32582651 248944523 227744016

输出

1 9 8 1 0

数据范围与提示

本题共 4 个子任务，每个子任务分值 25，第 $k$ 个子任务满足 $n \le 10^{k+1}$。