问个问题QwQ

P4245 【模板】任意模数多项式乘法

Piwry @ 2020-01-15 10:59:59

题解中许多都是用几个卷积拼成答案；

也就是说如果数据范围够小只要直接求积然后每个系数%M就行了，

但数据范围大时为了保证精度所以要拼起来是么QAQ

by this_red_is_gone @ 2020-01-15 11:19:07

因为直接FFT，系数位数高达23位，精度炸飞，所以拆系数

by 辰星凌 @ 2020-01-15 11:24:55

Orz NTT巨捞

by 皎月半洒花 @ 2020-01-15 11:57:55

@Piwry 其实有两点考虑，你说的是其中之一。由于只要保证最后取模的数大于 10^{23} 就可以不发生取模运算，所以可以保证正确。其次NTT需要的是NTT模数，需要 2^n|(p-1)，所以最后拆成 3 个乘积大于 10^{23} 的NTT模数。

至于为什么选三个？首先，常数优；其次，你必须要保证前两个乘起来不爆 \rm long ~long 才能简单地合并。综上，选三个最优。

by Piwry @ 2020-01-15 16:52:46

@皎月半洒花

~~ORZ是花姐姐~~

了解了，十分感谢！