本文作者为 JustinRochester。
任意模数多项式乘法
在部分题目中,我们的多项式运算结果并不是对多项式模数(如 \(998244353\))取模,而是对一些指定的(甚至是非质数的模数)取模。
为了解决这个问题,我们引入任意模数的多项式乘法。
首先需要明确的是:任意模数意义下的多项式乘法,是转化成我们先前讲过的多项式乘法的。
为此,我们需要清楚地知道:当且仅当两个模 \(M\) 意义下的多项式经过模 \(M\) 乘法,能得到一个模 \(M\) 意义下的多项式。
也就是说,假设我们有三个模 \(M\) 意义下的多项式 \(A(x), B(x), C(x)\) ,我们计算 \(A(x), B(x)\) 的模 \(M\) 意义下的乘法步骤是:
- 将 \(A(x), B(x)\) 的模 \(M\) 乘法转化为普通乘法的问题;
- 计算普通乘法问题;
- 将普通乘法结果还原为原多项式。
而计算三者模 \(M\) 乘积的步骤是:
- 计算其中两个的模 \(M\) 乘积;
- 计算乘积结果和剩下那个多项式的模 \(M\) 乘积。