提交记录 11899


用户 题目 状态 得分 用时 内存 语言 代码长度
hly1204 1002. 测测你的多项式乘法 Compile Error 0 0 ns 0 KB C++ 2.59 KB
提交时间 评测时间
2020-02-24 11:00:26 2020-08-01 02:48:54
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=4e5+5;
const double PI=acos(-1.0);
struct Complex{
    double real,imag;
    Complex(double a=0,double b=0):real(a),imag(b){}
    Complex(const Complex &a):real(a.real),imag(a.imag){}
    Complex conj()const{return Complex(real,-imag);}
    Complex &operator=(const Complex &a){real=a.real,imag=a.imag;return *this;}
    Complex &operator+=(const Complex &a){real+=a.real,imag+=a.imag;return *this;}
    Complex &operator-=(const Complex &a){real-=a.real,imag-=a.imag;return *this;}
    Complex &operator*=(const Complex &a){
        double tmp1=real*a.real-imag*a.imag,tmp2=real*a.imag+imag*a.real;
        real=tmp1,imag=tmp2;return *this;
    }
    Complex &operator/=(const Complex &a){
        double tmp1=(real*a.real+imag*a.imag)/(a.real*a.real+a.imag*a.imag),
        tmp2=(imag*a.real-real*a.imag)/(a.real*a.real+a.imag*a.imag);
        real=tmp1,imag=tmp2;return *this;
    }
    friend Complex operator+(const Complex &a,const Complex &b){Complex c(a);return c+=b;}
    friend Complex operator-(const Complex &a,const Complex &b){Complex c(a);return c-=b;}
    friend Complex operator*(const Complex &a,const Complex &b){Complex c(a);return c*=b;}
    friend Complex operator/(const Complex &a,const Complex &b){Complex c(a);return c/=b;}
}eps[N],a[N],b[N];
void init(int n){
    int l=n>>1;
    for(int i=0;i<l;++i){
        eps[l+i].real=cos(i*PI/l);
        eps[l+i].imag=sin(i*PI/l);
    }
    while(l>>=1){
        for(int i=0;i<l;++i){
            eps[l+i]=eps[l+i<<1];
        }
    }
}
void dft(int n,Complex x[]){
    for(int i=0,j=0;i<n;++i){
        if(i<j)swap(x[i],x[j]);
        for(int k=n>>1;(j^=k)<k;k>>=1){}
    }
    for(int i=2;i<=n;i<<=1){
        int l=i>>1;
        for(int j=0;j<n;j+=i){
            for(int k=0;k<l;++k){
                Complex u=x[k+j],v=eps[l+k]*x[k+j+l];
                x[k+j]=u+v;
                x[k+j+l]=u-v;
            }
        }
    }
}
void idft(int n,Complex x[]){
    reverse(x+1,x+n);
    dft(n,x);
    for(int i=0;i<n;++i)x[i]/=n;
}
int main(){
#ifdef LOCAL
    freopen("..\\in","r",stdin),freopen("..\\out","w",stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    cin>>n>>m;
    int t;
    for(int i=0;i<=n;++i){
        cin>>t;
        a[i].real=t;
    }
    for(int i=0;i<=m;++i){
        cin>>t;
        a[i].imag=t;
    }
    int len=1;
    while(len<n+m+2)len<<=1;
    init(len);
    dft(len,a);
    for(int i=0;i<len;++i){
        a[i]*=a[i];
    }
    idft(len,a);
    for(int i=0;i<=n+m;++i){
        cout<<static_cast<int>(a[i].imag/2.0+0.5)<<' ';
    }
    return 0;
}

CompilationN/AN/ACompile ErrorScore: N/A


Judge Duck Online | 评测鸭在线
Server Time: 2024-03-28 20:08:32 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用