求助运行问题
查看原帖
求助运行问题
537046
大眼仔Happy楼主2023/8/2 20:46

rt,调了很久才发现的一个问题,但不知道为什么这样会CE

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
const int N=3e6+5;
const db pi=acos(-1.0);
int n,m,up=1;
struct cp
{
    db real,imag;
    cp friend operator +(const cp A,const cp B)
    {
        cp res;
        res.real=A.real+B.real;
        res.imag=A.imag+B.imag;
        return res; 
    }
    cp friend operator -(const cp A,const cp B)
    {
        cp res;
        res.real=A.real-B.real;
        res.imag=A.imag-B.imag;
    }
    cp friend operator *(const cp A,const cp B)
    {
        cp res;
        res.real=A.real*B.real-A.imag*B.imag;
        res.imag=A.real*B.imag+A.imag*B.real;
        return res;
    }
};
vector<cp>F,G;
vector<cp> DFT(vector<cp> A)
{
    if(A.size()==1)return A;
    int len=A.size();
    vector<cp>F0,F1;
    F0.resize(len/2);
    for(int i=0;i<len;i+=2)F0[i/2]=A[i];
    F1.resize(len/2);
    for(int i=1;i<len;i+=2)F1[i/2]=A[i];
    vector<cp>S,S0=DFT(F0),S1=DFT(F1);
    S.resize(len);
    cp w=(cp){cos(2*pi/len),sin(2*pi/len)},idw=(cp){1,0};
    for(int i=0;i<len;i++)
    {
        int id=i%(len/2);
        S[i]=S0[id]+idw*S1[id];
        idw=idw*w;
    }
    return S;
}
vector<cp> IDFT(vector<cp> A)
{
    vector<cp> S=DFT(A);
    int len=S.size();
    reverse(&S[1],&S[len]);
    for(int i=0;i<len;i++)S[i].real/=len,S[i].imag/=len;
    return S;
}
void calc()
{
	F=DFT(F);G=DFT(G);
    printf("ok");
    for(int i=0;i<up;i++)F[i]=F[i]*G[i];
    F=IDFT(F);
}
int main(){                                               
    scanf("%d%d",&n,&m);
    while(up<n+m+1)up<<=1;
    F.resize(up);G.resize(up);
    for(int i=0;i<=n;i++)scanf("%d",&F[i].real);
    for(int i=0;i<=m;i++)scanf("%d",&G[i].real);
    printf("hello1");
    calc();
    for(int i=0;i<n+m+1;i++)printf("%d ",int(F[i].real+0.5));
    return 0;
}

而将calc()里面的东西拿到主函数里面就可以运行并且过样例了。

2023/8/2 20:46
加载中...