提交记录 6792


用户 题目 状态 得分 用时 内存 语言 代码长度
SovietPower 1002i. 【模板题】多项式乘法 Accepted 100 64.551 ms 4692 KB C++ 1.51 KB
提交时间 评测时间
2018-11-05 22:09:34 2020-08-01 00:50:02
//仅用于测试
#include<cmath>
#include<cstdio>
#include<algorithm>
#define mod 998244353
#define gg 3
#define ll long long
#define N 440000
using namespace std;
inline char gc(){
    static char now[1<<16],*S,*T;
    if (T==S) {T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
    return *S++;
}
inline int read(){
    int x=0,f=1;char ch=gc();
    while(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();}
    while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=gc();
    return x*f;
}
inline int ksm(int base,int t){
    int tmp=1;
    for (;t;t>>=1,base=(ll)base*base%mod) if (t&1) tmp=(ll)tmp*base%mod;return tmp;
}
int n,m,R[N],a[N],b[N];
inline void ntt(int *x,int f){
    for (int i=0;i<n;++i) if (i<R[i]) swap(x[i],x[R[i]]);
    for (int i=1;i<n;i<<=1){
        ll wn=ksm(gg,f==1?(mod-1)/(i<<1):mod-1-(mod-1)/(i<<1));
        for (int j=0;j<n;j+=(i<<1)){    
            ll w=1;
            for (int k=0;k<i;++k,(w*=wn)%=mod){
                int t1=x[j+k],t2=x[j+i+k];t2=(ll)t2*w%mod;
                x[j+k]=t1+t2>mod?t1+t2-mod:t1+t2;
                x[j+i+k]=t1-t2<0?t1-t2+mod:t1-t2;
            }
        }
    }
}
int main(){
    n=read();m=read();
    for (int i=0;i<=n;++i) a[i]=read();
    for (int i=0;i<=m;++i) b[i]=read();m=n+m;for (n=1;n<=m;n<<=1);int l=log2(n);
    for (int i=0;i<n;++i) R[i]=(R[i>>1]>>1)|((i&1)<<l-1);
    ntt(a,1);ntt(b,1);
    for (int i=0;i<n;++i) a[i]=(ll)a[i]*b[i]%mod;
    ntt(a,-1);int inv=ksm(n,mod-2);
    for (int i=0;i<n;++i) a[i]=(ll)a[i]*inv%mod;
    for (int i=0;i<=m;++i) printf("%d ",a[i]);
    return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Subtask #1 Testcase #19.66 us28 KBAcceptedScore: 0

Subtask #1 Testcase #263.859 ms4 MB + 516 KBAcceptedScore: 100

Subtask #1 Testcase #329.157 ms1 MB + 880 KBAcceptedScore: 0

Subtask #1 Testcase #429.232 ms1 MB + 868 KBAcceptedScore: 0

Subtask #1 Testcase #510.45 us28 KBAcceptedScore: 0

Subtask #1 Testcase #610.06 us28 KBAcceptedScore: 0

Subtask #1 Testcase #710.17 us28 KBAcceptedScore: 0

Subtask #1 Testcase #858.931 ms4 MB + 248 KBAcceptedScore: 0

Subtask #1 Testcase #958.831 ms4 MB + 248 KBAcceptedScore: 0

Subtask #1 Testcase #1053.777 ms3 MB + 1004 KBAcceptedScore: 0

Subtask #1 Testcase #1164.083 ms4 MB + 596 KBAcceptedScore: 0

Subtask #1 Testcase #1264.551 ms3 MB + 476 KBAcceptedScore: 0

Subtask #1 Testcase #138.96 us28 KBAcceptedScore: 0


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