A2568. 任意模数多项式乘法逆
编程题
省选/NOI-
知识点
题目描述
给定一个多项式 $F(x)$ ，请求出一个多项式 $G(x)$ ， 满足 $F(x) * G(x) \equiv 1 ( \mathrm{mod\:} x^n )$
。系数对 $10^9+7$ 取模。
。系数对 $10^9+7$ 取模。
输入格式
首先输入一个整数 $n$， 表示输入 $F(x)$ 为 $n-1$ 次。
接着输入 $n$ 个整数，第 $i$ 个整数 $a_i$ 代表 $F(x)$ 次数为 $i-1$ 项的系数。
接着输入 $n$ 个整数，第 $i$ 个整数 $a_i$ 代表 $F(x)$ 次数为 $i-1$ 项的系数。
输出格式
输出 $n$ 个数字，第 $i$ 个整数 $b_i$ 代表 $G(x)$ 次数为 $i-1$ 的项的系数。
输入输出样例
输入 #1
5 1 6 3 4 9
输出 #1
1 1000000001 33 999999823 1020
说明/提示
$1 \leq n \leq 10^5$，$0 \leq a_i \leq 10^9$。