本文作者为 JustinRochester。

目录地址

上一篇

下一篇

任意模数多项式乘法

在部分题目中，我们的多项式运算结果并不是对多项式模数（如 \(998244353\)）取模，而是对一些指定的（甚至是非质数的模数）取模。

为了解决这个问题，我们引入任意模数的多项式乘法。

首先需要明确的是：任意模数意义下的多项式乘法，是转化成我们先前讲过的多项式乘法的。

为此，我们需要清楚地知道：当且仅当两个模 \(M\) 意义下的多项式经过模 \(M\) 乘法，能得到一个模 \(M\) 意义下的多项式。

也就是说，假设我们有三个模 \(M\) 意义下的多项式 \(A(x), B(x), C(x)\) ，我们计算 \(A(x), B(x)\) 的模 \(M\) 意义下的乘法步骤是：

1. 将 \(A(x), B(x)\) 的模 \(M\) 乘法转化为普通乘法的问题；
2. 计算普通乘法问题；
3. 将普通乘法结果还原为原多项式。

而计算三者模 \(M\) 乘积的步骤是：

1. 计算其中两个的模 \(M\) 乘积；
2. 计算乘积结果和剩下那个多项式的模 \(M\) 乘积。