多项式算法5:多项式求逆
多项式求逆
前置知识: FFT NTT
多项式求逆
这里的多项式求逆,其实是求多项式的逆元。 对于多项式
A
(
x
)
A(x)
A(x),如果存在
A
(
x
)
B
(
x
)
≡
1
(
m
o
d
x
n
)
A(x)B(x) \equiv 1( \mod x^n )
A(x)B(x)≡1(modxn),那么我们称
B
(
x
)
B(x)
B(x)为
A
(
x
)
A(x)
A(x)在模
x
n
x^n
xn意义下的逆元。 这里的模
x
n
x^n
xn是指舍弃所有
x
x
x的次数大于等于
n
n
n的项,当然也可以理解为所有
x
x
x的次数大于等于
n
n
n的项的系数赋为零。 例如,多项式
x
4
+
4
x
3
+
6
x
2
+
4
x
+
1
x^4+4x^3+6x^2+4x+1
x4+4x3+6x2+4x+1对
x
3
x^3
x3取模后变为
6
x
2
+
4
x
+
1
6x^2+4x+1
6x2+4x+1。 当
A
(
x
)
B
(
x
)
≡
1
(
m
o
d
x
n
)
A(x)B(x) \equiv 1( \mod x^n )
A(x)B(x)≡1(modxn),表示
A
(
x
)
A(x)
A(x)和
B
(
x
)
B(x)
B(x)在模
x
n
x^n
xn的意义下相乘得到的多项式,只有常数项为
1
1
1,其它项的系数均为
0
0
0。 小结论:如果满足
A
(
x
)
B
(
x
)
≡
1
(
m
o
d
x
n
)
A(x)B(x) \equiv 1( \mod x^n )
A(x)B(x)≡1(modxn),那么对于
1
≤
m
<
n
1 \le m \lt n
1≤m |