首先定义多项式的度数 $degA$ 为多项式 $A(x)$ 的最高次数

那么多项式 $A(x)$ 的逆即为存在多项式 $B(x)$ 使得条件满足：
$$
A(x)B(x) \equiv 1 \pmod{x^n}
$$

求解过程

分治 $FFT$

对 $A(x) = \sum\limits_{k = 0}^{n - 1} a_kx^k, B(x) = \sum\limits_{k = 0}^{n - 1} b_kx^k$

从常数项考虑，有 $b_0 = \frac1{a_0}$，则由 $\sum\limits_{k = 0}^n b_ka_{n - k} = 0$ 可得
$$
b_k = \sum\limits_{i = 0}^{k - 1} b_i\left(- \frac{a_{k - i}}{a_0}\right)
$$

倍增迭代

假设存在多项式 $A(x)$ ，以及其逆 $B(x)$ 满足条件 ，那么必定有$A(x)B(x) \equiv 1 \pmod{x^{\left\lceil\frac{n}{2}\right\rceil}} … (1)$ ，因为 $x^n$ 是 $x^{\left\lceil\frac{n}{2}\right\rceil}$ 的倍数

并且存在 $A(x)B’(x) \equiv 1 \pmod{x^{\left\lceil\frac{n}{2}\right\rceil}} … (2)$

$(1) - (2)$ ，得
$$
\begin{aligned} B(x) - B’(x) &\equiv 0 \pmod{x^{\left\lceil\frac{n}{2}\right\rceil}} … (3) \\ B(x)^2 - 2B(x)B’(x) + B’(x)^2 &\equiv 0 \pmod{x^n} \end{aligned}
$$
上一步解释一下，是两边平方

至于为什么模数也需要平方，是因为 $(3)$ 式满足左边的多项式在其模意义下为 $0$ ，且式子恒成立，故其除了第 $x^{\left\lceil\frac{n}{2}\right\rceil}$ 项其余系数皆为 $0$ ，那么现在考虑 $0 \le x \le n - 1$ ，又因为 $a_i = \sum\limits_{j = 1}^i a_j b_{i - j}$ ，所以必定存在 $i$ 或者 $i - j$ 小于 $x^{\left\lceil\frac{n}{2}\right\rceil}$ ，故 $a_i = 0$ ，所以平方无妨

同乘 $A(x)$ ，移项，得
$$
B(x) \equiv 2B’(x) - A(x)B’(x)^2 \pmod{x^n}
$$
在递归过程中最后会递归到 $n = 1$ ，那么此时 $A(x)B’’(x) \equiv c \pmod{x}$ ，取 $c^{- 1}$ 就好了

那么再用 $FFT$ 优化就可以做到 $O (n \log n)$ 求解

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <iostream>
#include <cstdio>
#include <cstring>

#define MOD 998244353
#define g 3

using namespace std;

typedef long long LL;

const int MAXN = 4e05 + 10;

LL power (LL x, int p) {
	LL cnt = 1;
	while (p) {
		if (p & 1)
			cnt = cnt * x % MOD;
		x = x * x % MOD;
		p >>= 1;
	}
	return cnt;
}
const LL invg = power (g, MOD - 2);

int N;
LL f[MAXN], invf[MAXN]= {0};

LL A[MAXN]= {0}, B[MAXN]= {0};
int oppo[MAXN]= {0};
int limit;
void NTT (LL* a, int inv) {
	for (int i = 0; i < limit; i ++)
		if (i < oppo[i])
			swap (a[i], a[oppo[i]]);
	for (int mid = 1; mid < limit; mid <<= 1) {
		LL omega = power (inv == 1 ? g : invg, (MOD - 1) / (mid << 1));
		for (int n = mid << 1, j = 0; j < limit; j += n) {
			LL x = 1;
			for (int k = 0; k < mid; k ++, x = x * omega % MOD) {
				LL a1 = a[j + k], xa2 = x * a[j + k + mid] % MOD;
				a[j + k] = (a1 + xa2) % MOD;
				a[j + k + mid] = (a1 - xa2 + MOD) % MOD;
			}
		}
	}
}
void Inverse (int deg, LL* ps) {
	if (deg == 1) {
		ps[0] = power (f[0], MOD - 2);
		return ;
	}
	Inverse ((deg + 1) >> 1, ps);
	int n, lim;
	for (n = 1, lim = 0; n < (deg << 1); n <<= 1, lim ++);
	limit = n;
	for (int i = 0; i < limit; i ++)
		oppo[i] = (oppo[i >> 1] >> 1) | ((i & 1) << (lim - 1));
	for (int i = 0; i < limit; i ++)
		A[i] = B[i] = 0;
	for (int i = 0; i < deg; i ++)
		A[i] = f[i];
	for (int i = 0; i < deg << 1; i ++)
		B[i] = ps[i];
	NTT (A, 1), NTT (B, 1);
	for (int i = 0; i < limit; i ++)
		B[i] = B[i] * ((2ll - A[i] * B[i] % MOD + MOD) % MOD) % MOD;
	NTT (B, - 1);
	LL invn = power (n, MOD - 2);
	for (int i = 0; i < deg; i ++)
		ps[i] = B[i] * invn % MOD;
}

int getnum () {
	int num = 0;
	char ch = getchar ();

	while (! isdigit (ch))
		ch = getchar ();
	while (isdigit (ch))
		num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();

	return num;
}

int main () {
	N = getnum ();
	for (int i = 0; i < N; i ++)
		f[i] = getnum ();
	Inverse (N, invf);
	for (int i = 0; i < N; i ++) {
		if (i > 0)
			putchar (' ');
		printf ("%lld", invf[i]);
	}
	puts ("");

	return 0;
}

/*
5
1 6 3 4 9
*/

/*
10
2 3 3 3 1233 211 23 3 3 322
*/