三模数全T!!快救救孩子吧

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

lxd150039 @ 2019-06-28 23:58:58

#include<iostream> 
#include<cstdio> 
#define ll long long
#define ma 400000
using namespace std;
ll a[3][ma],b[3][ma],x,p[]={998244353,167772161,1004535809};
ll mx,my,mz,pp,ans[ma];
int n,m,len,r[ma];
ll mul(ll a, ll b,ll p)
{
    ll ans=0;
    a%=p; b%=p;
    while(a)
    {
        if(a&1) ans+=b;
        a>>=1; b<<=1; b%=p; ans%=p;
    }
    return ans;
}
ll deal(ll a,ll b,ll p)
{
    ll ans=1;   a%=p;
    while(b)
    {
        if(b&1) ans=mul(ans,a,p);
        a=mul(a,a,p); b>>=1;
    }
    return ans;
}
void fft(ll *f,ll flag,ll p)
{
    for(int i=0;i<n;i++) if(i<r[i]) swap(f[i],f[r[i]]);
    for(int i=1;i<n;i<<=1)
    {
        ll m1=deal(flag,(p-1)/(2*i),p);
        for(int j=0;j<n;j+=2*i)
        {
            ll m2=1;
            for(int k=0;k<i;k++,m2=mul(m2,m1,p))
            {
                mx=f[j+k]; my=mul(f[j+k+i],m2,p);
                f[j+k]=(mx+my)%p; f[j+k+i]=(mx-my+p)%p;
            }
        }
    }
}
int main()
{
    scanf("%d%d%lld",&n,&m,&pp);
    for(int i=0;i<=n;i++) scanf("%lld",&x),a[0][i]=a[1][i]=a[2][i]=x;
    for(int i=0;i<=m;i++)   scanf("%lld",&x),b[0][i]=b[1][i]=b[2][i]=x;

    m=n+m+1; n=1; len=0;
    while(n<m) n<<=1,len++;
    for(int i=1;i<n;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(len-1));
    for(int i=0;i<3;i++)
    {
        fft(&a[i][0],3,p[i]); fft(&b[i][0],3,p[i]);
        for(int j=0;j<n;j++) a[i][j]=mul(a[i][j],b[i][j],p[i]);
        fft(&a[i][0],deal(3,p[i]-2,p[i]),p[i]); 
        x=deal(n,p[i]-2,p[i]);  
        for(int j=0;j<m;j++) a[i][j]=mul(x,a[i][j],p[i]);
    } 
    for(int j=0;j<m;j++)
    {
        mx=deal(p[0],p[1]-2,p[1]); mx=mul(a[1][j]-a[0][j]+p[1],mx,p[1]);//k
        my=(a[2][j]-a[0][j]-mul(mul(p[0],p[1],p[2]),mx,p[2])+2*p[2])%p[2];//x'-x
        mz=mul(p[0],p[1],p[2]); mz=deal(my,p[2]-2,p[2]);//ab逆元 
        my=(mul(mul(p[0],p[1],pp),mul(mz,my,p[2]),pp)+a[0][j]+mul(mx,p[0],pp))%pp;
        printf("%lld ",my);
    }   
}  

不知道为什么全t了,如果有人知道的话麻烦联系下我。感激不尽。


by NaCly_Fish @ 2019-06-29 01:45:32

@lxd150039 不要用三模,需要⑨次NTT,太慢了


by NaCly_Fish @ 2019-06-29 01:46:27

还是4次FFT的比较块


by disangan233 @ 2019-06-29 08:07:39

@NaCly_Fish 我觉得三模数ntt不慢啊。


by disangan233 @ 2019-06-29 08:09:20

虽然我太菜了跑了7000ms


by lxd150039 @ 2019-06-29 10:14:04

@NaCly_Fish 这也不至于全T了吧。。。。。。


|