首先定义多项式的度数 (degA) 为多项式 (A(x)) 的最高次数
那么多项式 (A(x)) 的逆即为存在多项式 (B(x)) 使得条件满足：
[A(x)B(x) equiv 1 pmod{x^n}
]
求解过程
假设存在多项式 (A(x)) ，以及其逆 (B(x)) 满足条件 ，那么必定有(A(x)B(x) equiv 1 pmod{x^{leftlceilfrac{n}{2} ight ceil}} ... (1)) ，因为 (x^n) 是 (x^{leftlceilfrac{n}{2} ight ceil}) 的倍数
并且存在 (A(x)B'(x) equiv 1 pmod{x^{leftlceilfrac{n}{2} ight ceil}} ... (2))
((1) - (2)) ，得
[egin{aligned} B(x) - B'(x) &equiv 0 pmod{x^{leftlceilfrac{n}{2}
ight
ceil}} ... (3) \ B(x)^2 - 2B(x)B'(x) + B'(x)^2 &equiv 0 pmod{x^n} end{aligned}
]
上一步解释一下，是两边平方
至于为什么模数也需要平方，是因为 ((3)) 式满足左边的多项式在其模意义下为 (0) ，且式子恒成立，故其除了第 (x^{leftlceilfrac{n}{2} ight ceil}) 项其余系数皆为 (0) ，那么现在考虑 (0 le x le n - 1) ，又因为 (a_i = sumlimits_{j = 1}^i a_j b_{i - j}) ，所以必定存在 (i) 或者 (i - j) 小于 (x^{leftlceilfrac{n}{2} ight ceil}) ，故 (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)) 求解
代码
#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
*/