只对样例求调,马蜂不错
查看原帖
只对样例求调,马蜂不错
596437
Raisen_zx楼主2024/4/15 20:27

仿照第二篇题解的写法,但是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;
}
2024/4/15 20:27
加载中...