提交记录 11902


用户 题目 状态 得分 用时 内存 语言 代码长度
hly1204 1002. 测测你的多项式乘法 Compile Error 0 0 ns 0 KB C++11 1.47 KB
提交时间 评测时间
2020-02-24 12:30:17 2020-08-01 02:48:57
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=4e6+5;
const int P=119<<23|1,G=3;
ll eps[N],a[N],b[N];
ll qpow(ll x,ll y){
    ll ans=1;
    for(;y;y>>=1){
        if(y&1)ans=ans*x%P;
        x=x*x%P;
    }
    return ans;
}
ll inv(ll x){
    return qpow(x,P-2);
}
void init(int n){
    ll g=qpow(G,(P-1)/n);
    int l=n>>1;
    eps[l]=1;
    for(int i=1;i<l;++i){
        eps[l+i]=eps[l+i-1]*g%P;
    }
    while(l>>=1){
        for(int i=0;i<l;++i){
            eps[l+i]=eps[l+i<<1];
        }
    }
}
void dft(int n,ll 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){
                ll u=x[j+k],v=eps[l+k]*x[j+k+l]%P;
                x[j+k]=(u+v)%P;
                x[j+k+l]=(u-v+P)%P;
            }
        }
    }
}
void idft(int n,ll x[]){
    reverse(x+1,x+n);
    dft(n,x);
    ll in=inv(n);
    for(int i=0;i<n;++i)x[i]=x[i]*in%P;
}
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;
    for(int i=0;i<=n;++i)cin>>a[i];
    for(int i=0;i<=m;++i)cin>>b[i];
    int len=1;
    while(len<n+m+2)len<<=1;
    init(len);
    dft(len,a),dft(len,b);
    for(int i=0;i<len;++i)(a[i]*=b[i])%=P;
    idft(len,a);
    for(int i=0;i<=n+m;++i)cout<<a[i]<<' ';
    return 0;
}

CompilationN/AN/ACompile ErrorScore: N/A


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