#172. 多项式欧几里得

内存限制:512 MiB 时间限制:6000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: EntropyIncreaser

题目描述

这是一道模板题。

给你一个次数为 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

样例输出 1

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 = 10^{k+1}