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了吧。。。。。。