3942: 多项式欧几里得
内存限制：512 MB
时间限制：6.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
这是一道模板题。
给你一个次数为 $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)$ 的各项系数。
样例输入 复制
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
输出样例2
1 9 8 1 0
数据范围：本题共 $4$ 个子任务，每个子任务分值 $25$，第 $k$ 个子任务满足 $n \leq 10^{k+1}$。