任意模数多项式乘法

NTT

因为任意模数多项式乘法的系数可能超过了 所以一般的 就做不了。所以对于 的做法是找到 个模数，最后使用 合并一下，但是这里的合并中的答案可能超过 的值域，所以要用快速乘实现。

FFT

任意模数多项式乘法用 实现的问题主要是因为精度问题，这里使用了 次变化的 实现，采用了 作为底，那么一个多项式，我们根据 。那么 。就拆分成了系数比较小的四个多项式。最后合并一下就好了。

代码

这里只给出了 的代码实现。

#include<bits/stdc++.h>
using namespace std;
const int N = 4e5 + 100,base = 1 << 15;
#define db long double 
#define ll long long
const db pi = acos(-1);
int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch=='-')f=1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    return f?-x:x;
}
struct comp{
    db x,y;
    comp(db a,db b) {x=a;y=b;}
    comp() {x=y=0;}
    comp operator + (const comp a) const {return comp(x+a.x,y+a.y);}
    comp operator - (const comp a) const {return comp(x-a.x,y-a.y);}
    comp operator * (const comp a) const {return comp(a.x*x-a.y*y,y*a.x+a.y*x);}
}A1[N],A2[N],B1[N],B2[N];
int limit = 1,L,r[N],n,m,p;
void fft(comp *a,int type) {
    for(int i = 0;i < limit;i++) if(r[i] < i) swap(a[r[i]],a[i]);
    for(int mid = 1;mid < limit;mid <<= 1) {
        comp wn = comp(cos(1.0 * pi / mid),type * sin(1.0 * pi / mid));
        for(int i = 0;i < limit;i += (mid << 1)) {
            comp w = comp(1,0);
            for(int j = 0;j < mid;j++,w = w * wn) {
                comp x = a[i + j],y = w * a[i + j + mid];
                a[i + j] = x + y;a[i + j + mid] = x - y;
            }
        }
    }
    if(type == -1) for(int i = 0;i < limit;i++) a[i].x = a[i].x / limit;
}
void Merge(comp *a,comp *b,int B,int *f) {
    static comp g[N];
    for(int i = 0;i < limit;i++) g[i] = a[i] * b[i];fft(g,-1);
    for(int i = 0;i < limit;i++) f[i] = (f[i] + 1ll * B * ((ll)floor(g[i].x + 0.5) % p) % p) % p;
}
void MTT(comp *a,comp *b,comp *c,comp *d,int *f) {
    fft(a,1);fft(b,1);fft(c,1);fft(d,1);
    Merge(a,c,base * 1ll * base % p,f);Merge(a,d,base % p,f);
    Merge(b,c,base % p,f);Merge(b,d,1,f);
}
int main() {
    n = read();m = read();p = read();
    for(int i = 0,x;i <= n;i++) {x = read();A1[i].x = x / base;B1[i].x = x % base;} 
    for(int i = 0,x;i <= m;i++) {x = read();A2[i].x = x / base;B2[i].x = x % base;}
    while(limit <= n + m) limit <<= 1,L++;
    for(int i = 0;i < limit;i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << L - 1);
    static int Ans[N];memset(Ans,0,sizeof(Ans));
    MTT(A1,B1,A2,B2,Ans);
    for(int i = 0;i <= n + m;i++) printf("%d ",Ans[i]);
    return 0 & printf("\n");
}