提交记录 7626


用户 题目 状态 得分 用时 内存 语言 代码长度
chenhoujin 1002i. 【模板题】多项式乘法 Accepted 100 69.697 ms 4628 KB C++ 1.62 KB
提交时间 评测时间
2019-01-25 09:17:00 2020-08-01 01:06:34
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=400000+5, mod=998244353, gen=3;
int a[N], b[N], rev[N];

inline int read()
{
    int x=0,f=1;char ch=getchar();
    for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
    for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
    return x*f;
}

int power(ll x, int t)
{
    ll res=1;
    while (t)
    {
        if (t&1) res=(ll)res*x%mod;
        x=(ll)x*x%mod; t>>=1;
    }
    return res;
}

inline void NTT(int *a, int lim, int typ)
{
    for (register int i=0; i<lim; i++) 
        if (i<rev[i]) swap(a[i], a[rev[i]]);
    for (register int mid=1, len=mid<<1; mid<lim; mid<<=1, len=mid<<1)
    {
        ll gn=power(gen, (mod-1)/len);
        for (register int now=0; now<lim; now+=len)
        {
            ll g=1;
            for (register int j=0; j<mid; j++, g=(ll)g*gn%mod)
            {
                int a1=a[now+j], a2=((ll)g*a[now+j+mid])%mod;
                a[now+j]=((ll)a1+a2)%mod; a[now+j+mid]=((ll)a1-a2+mod)%mod;
            }
        }
    }
    if (typ==-1) reverse(a+1, a+lim);
}

signed main()
{
    int n=read(), m=read(), lim=1, cnt=0; 
    while (lim<=n+m) lim<<=1, cnt++;
    for (register int i=0; i<=n; i++) a[i]=read();
    for (register int i=0; i<=m; i++) b[i]=read();
    for (register int i=0; i<=lim; i++) 
        rev[i]=(rev[i>>1]>>1)|((i&1)<<(cnt-1));
    NTT(a, lim, 1); NTT(b, lim, 1);
    for (register int i=0; i<=lim; i++) a[i]=((ll)a[i]*b[i])%mod;
    NTT(a, lim, -1);
    lim=power(lim, mod-2);
    for (register int i=0; i<=n+m; i++) 
        printf("%d ", (ll)a[i]*lim%mod);
    return 0;
}


CompilationN/AN/ACompile OKScore: N/A

Subtask #1 Testcase #18.87 us24 KBAcceptedScore: 0

Subtask #1 Testcase #269.339 ms4 MB + 452 KBAcceptedScore: 0

Subtask #1 Testcase #331.878 ms1 MB + 816 KBAcceptedScore: 100

Subtask #1 Testcase #431.884 ms1 MB + 804 KBAcceptedScore: 0

Subtask #1 Testcase #59.9 us24 KBAcceptedScore: 0

Subtask #1 Testcase #69.31 us24 KBAcceptedScore: 0

Subtask #1 Testcase #78.83 us24 KBAcceptedScore: 0

Subtask #1 Testcase #864.189 ms4 MB + 184 KBAcceptedScore: 0

Subtask #1 Testcase #964.225 ms4 MB + 184 KBAcceptedScore: 0

Subtask #1 Testcase #1059.039 ms3 MB + 940 KBAcceptedScore: 0

Subtask #1 Testcase #1169.697 ms4 MB + 532 KBAcceptedScore: 0

Subtask #1 Testcase #1269.589 ms3 MB + 412 KBAcceptedScore: 0

Subtask #1 Testcase #138.1 us24 KBAcceptedScore: 0


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