仿照第二篇题解的写法,但是WA0
求dalao帮调
#include <cstdio>
#include <cmath>
#include <algorithm>
#include<iostream>
typedef long long ll;
typedef double ld;
const double PI = acos(-1);
const int MAXN = 600005;
using namespace std;
struct Complex{
double a, b;
Complex operator+(Complex o) const { return {a + o.a, b + o.b}; }
Complex operator-(Complex o) const { return {a - o.a, b - o.b}; }
Complex operator*(Complex o) const { return {a * o.a - b * o.b, a * o.b + b * o.a}; }
Complex operator/(double o) const { return {a/o, b/o}; }
Complex operator- ()const {return {a,-b};}
}a0[MAXN],a1[MAXN],Wn[MAXN],b0[MAXN],b1[MAXN],wn[MAXN],p[MAXN],q[MAXN];
const Complex I={0,1};
int n,m,L=1,rev[MAXN],B;
int mod;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9')
x=x*10+ch-'0',ch=getchar();
return x*f;
}
void FFT(Complex *a) {
for (int i = 1; i < L; ++i)
if (rev[i] > i)
swap(a[rev[i]], a[i]);
for (int p = 1; p < L; p <<= 1) {
Complex omeg{ cos(PI / p), sin(PI / p) };
for (int t = p << 1, i = 0; i < L; i += t) {
Complex tmp = { 1, 0 };
for (int j = 0; j < p; j++) {
Complex x = a[i + j], y = tmp * a[i + j + p];
a[i + j] = x + y, a[i + j + p] = x - y;
tmp = tmp * omeg;
}
}
}
}
void IFFT(Complex *a) {
for(int i=1;i<n;++i) if(i<n-i) swap(a[i],a[n-i]);
for (int i = 1; i < L; ++i)
if (rev[i] > i)
swap(a[rev[i]], a[i]);
for (int p = 1; p < L; p <<= 1) {
Complex omeg{ cos(PI / p), -1 * sin(PI / p) };
for (int t = p << 1, i = 0; i < L; i += t) {
Complex tmp = { 1, 0 };
for (int j = 0; j < p; j++) {
Complex x = a[i + j], y = tmp * a[i + j + p];
a[i + j] = x + y, a[i + j + p] = x - y;
tmp = tmp * omeg;
}
}
}
for (int i = 0; i < L; ++i) a[i] = a[i] / L;
}
inline void solve(Complex *a,Complex *b)
{
for(int i=0;i<L;++i) a[i]=a[i]+I*b[i];
FFT(a);
// for(int i=0;i<L;++i) printf("%lf %lf\n",a[i].a,a[i].b);
for (int i = 0; i < L; i++) b[i] = -(a[i ? L - i : 0]);
for (int i = 0; i < L; i++) {
Complex x = a[i], y = b[i];
a[i] = (x + y) /2.0;
b[i] = ((y - x) /2.0) * I;
}
}
inline long long qz(double d)
{
return d < 0 ? ll(d - 0.5) % mod : ll(d + 0.5) % mod;
}
int main()
{
scanf("%d%d%d",&n,&m,&mod);
n--;m--;
B=int(sqrt(mod)+1);
for(int i=0;i<=n;++i)
{
int x;
scanf("%d",&x);
x%=mod;
a0[i].a=x/B;
a1[i].a=x%B;
}
for(int i=0;i<=m;++i)
{
int x;
scanf("%d",&x);
x%=mod;
b0[i].a=x/B;
b1[i].a=x%B;
}
while(L<=n+m) L<<=1;
// for(int i=0;i<=L;++i) printf("%lf %lf %lf %lf\n",a0[i].a,a1[i].a,b0[i].a,b0[i].a);
for(int i=1;i<L;++i)
{
rev[i]=(rev[i>>1]>>1)+(i&1?L>>1:0);
}
solve(a0,a1);
solve(b0,b1);
for(int i=0;i<L;++i)
{
p[i]=a0[i]*b0[i]+I*a1[i]*b0[i];
q[i]=a0[i]*b1[i]+I*a1[i]*b1[i];
}
IFFT(p);
IFFT(q);
for(int i=0;i<=n+m;++i)
{
printf("%lld ",((B*B*qz(p[i].a))%mod+B*(qz(p[i].b)+qz(q[i].a))%mod+qz(q[i].b)+mod)%mod);
}
return 0;
}