调了一整天了,帮帮这个屑吧
查看原帖
调了一整天了,帮帮这个屑吧
173660
zhoukangyang楼主2020/5/2 21:20

#include<bits/stdc++.h>
#define double long double
#define int long long
using namespace std;
inline void write(int s){if (s>9) write(s/10);putchar(s%10+48);}
inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return x*f;
}
struct CP {double x,y;CP (double xx = 0, double yy = 0) {x = xx, y = yy;}};
CP operator + (CP a,CP b) {return CP(a.x+b.x,a.y+b.y);}
CP operator - (CP a,CP b) {return CP(a.x-b.x,a.y-b.y);}
CP operator * (CP a,CP b) {return CP(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
CP aa[300009],ab[300009],ba[300009],bb[300009],zjoi[300009],ynoi[300009],ioi[300009];
int n,m,p[300009],pp[300009],q,inn,mod;
char cha[300009],chb[300009];
double pi = acos(-1);
void fft(CP *f,int len,int flag) {
	if(len==1) return;
	fft(f,(len>>1),flag),fft(f+(len>>1),(len>>1),flag);
	CP ch,now;
	now.x=1,now.y=0,ch.x=cos(2*pi/len),ch.y=flag*sin(2*pi/len);
	for(int i = 0; i < (len>>1); i++) f[i]=(f[i]+(f[i+len/2]*now)),f[i+len/2]=(f[i]-(f[i+len/2]*now)-(f[i+len/2]*now)),now=now*ch;
}
signed main() {
	n=read(),m=read(),mod=read();
	q=n+m;
	for(int i = 0; i <= n; i++) inn=read(),aa[i]=(inn>>15),ab[i]=(inn&32767);
	for(int i = 0; i <= m; i++) inn=read(),ba[i]=(inn>>15),bb[i]=(inn&32767);
	for(n = m+n+1; n != (n&-n); n += (n&-n));
	for(int i = 0; i < n; i++) pp[i]=((pp[i>>1]>>1)|((i&1)*(n>>1)));
	for(int i = 0; i < n; i++) if(i<pp[i]) swap(aa[i],aa[pp[i]]),swap(ab[i],ab[pp[i]]);
	for(int i = 0; i < n; i++) if(i<pp[i]) swap(ba[i],ba[pp[i]]),swap(bb[i],bb[pp[i]]);
	fft(aa,n,1),fft(ab,n,1),fft(ba,n,1),fft(bb,n,1);
	for(int i = 0; i < n; i++) zjoi[i]=aa[i]*ba[i];
	for(int i = 0; i < n; i++) ynoi[i]=ab[i]*bb[i];
	for(int i = 0; i < n; i++) ioi[i]=aa[i]*bb[i]+ab[i]*ba[i];
	fft(zjoi,n,-1),fft(ynoi,n,-1),fft(ioi,n,-1);
	for(int i = 0; i < n; i++) zjoi[i].x/=n,zjoi[i].x+=0.5,ynoi[i].x/=n,ynoi[i].x+=0.5,ioi[i].x/=n,ioi[i].x+=0.5;
	for(int i = 0; i < n; i++) p[i]=(((int)(zjoi[i].x)%mod<<15)%mod*32768+(int)(ynoi[i].x)+((int)(ioi[i].x)%mod<<30)%mod)%mod;
	for(int i = 0; i <= q; i++) write(p[i]),putchar(' ');
	return 0;
}
2020/5/2 21:20
加载中...