洛谷P4245：【模板】MTT （CRT+三模数NTT）

2019-04-14 17:43发布生成海报

站内文章 / 模拟电子

16640 0

题目传送门：https://www.luogu.org/problemnew/show/P4245

题目分析：一道任意模数多项式乘法的模板题。可以写拆项+FFT，或者三模数NTT。我暂时只写了后者。具体做法是这样：先选取三个乘积在

10^{23}

以上的便于使用NTT的模数。在这里我选的是

m_{1} = 998244353 = 2^{23} * 119 + 1

，

m_{2} = 1004535809 = 2^{21} * 479 + 1

，

m_{3} = 469762049 = 2^{26} * 7 + 1

。选这三个模数的好处在于它们的原根都是

3

。然后用这三个模数做NTT，可以得到以下三条式子：

a n s \equiv c_{1} (\mod m_{1})

a n s \equiv c_{2} (\mod m_{2})

a n s \equiv c_{3} (\mod m_{3})

虽然这三条式子可以在

10^{23}

以内唯一固定

a n s

的值，但问题也随之而来：

m_{1} * m_{2} * m_{3}

很大，无法直接用long long存下，而用long double之类的则会丢失精度，所以无法用普通的CRT。难道要写高精度？不，有一种很妙的方法可以解决这个问题。首先注意到这里只有三个模数，而且两个模数乘起来是不会爆long long的，所以可以先合并前两条式子。根据CRT，有：

a n s \equiv (c_{1} m_{2} I n v (m_{2}, m_{1}) + c_{2} m_{1} I n v (m_{1}, m_{2})) (\mod m_{1} m_{2})

其中

I n v (x, y)

表示x关于y的逆元。这条式子涉及到两个很大的数相乘然后再取模，而直接相乘会爆long long。可以用

O (\log (m_{1} m_{2}))

的快速乘，或者

O (1)

转double后相乘。为了方便，把上式化成这样的形式：

a n s \equiv C (\mod M)

然后设：

a n s = x M + C = y m_{3} + c_{3}

接下来的部分才是精髓。我们求出

x

在

\mod m_{3}

意义下的值：