NTT任意模数模板（+O(1)快速乘）

• 记忆LL 发布于
• 1485 收藏

  NTT任意模数的方法其实有点取巧。 两个数列每个有n个数，每个数的大小最多是10^9。 如果没有模数，那么卷积过后每个位置的答案一定小于10^9*10^9*n,差不多是10^24左右 那么就有一个神奇的做法，选3个乘积大于10^24的NTT模数，分别做一次，得到每个位上模意义下的答案， 然后用中国剩余定理得到模上三个质数乘积的答案。 因为答案显然小于三个质数乘积，那么模上三个质数乘...