提交记录 4334
提交时间 |
评测时间 |
2018-07-19 22:09:15 |
2020-07-31 22:53:45 |
// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
using namespace std;
const int N=3000005;
const int mod=998244353;
int r[N],l,n,m,A[N],B[N],w[N];
int ksm(int a,int k)
{
int s=1,b=a;
for(;k;k>>=1,b=1ll*b*b%mod)
if(k&1) s=1ll*s*b%mod;
return s;
}
void NTT(int *P,int op)
{
for(int i=0;i<n;i++) if(i<r[i]) swap(P[i],P[r[i]]);
for(int i=1;i<n;i<<=1)
{
int W=ksm(3,(mod-1)/(i<<1));//3是998244353的一个原根
if(op<0) W=ksm(W,mod-2); w[0]=1;
for(int j=1;j<i;j++) w[j]=1ll*w[j-1]*W%mod;
for(int j=0,p=i<<1;j<n;j+=p)
for(int k=0;k<i;k++)
{
int X=P[j+k],Y=1ll*w[k]*P[i+j+k]%mod;
P[j+k]=(X+Y)%mod;P[i+j+k]=(X-Y+mod)%mod;
}
}
if(op<0) for(int i=0,inv=ksm(n,mod-2);i<n;i++)
P[i]=1ll*P[i]*inv%mod;
}
int main()
{
cin>>n>>m;
for(int i=0;i<=n;i++) cin>>A[i];
for(int i=0;i<=m;i++) cin>>B[i];
m=n+m;for(n=1;n<=m;n<<=1) l++;l--;
for(int i=0;i<n;i++) r[i]=(r[i>>1]>>1)|((i&1)<<l);
NTT(A,1);NTT(B,1);for(int i=0;i<n;i++) A[i]=1ll*A[i]*B[i]%mod;NTT(A,-1);
for(int i=0;i<=m;i++) printf("%d ",A[i]);
return 0;
}
Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
Subtask #1 Testcase #1 | 38.9 us | 52 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #2 | 75.241 ms | 4 MB + 992 KB | Accepted | Score: 100 | 显示更多 |
Subtask #1 Testcase #3 | 35.265 ms | 2 MB + 76 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #4 | 35.232 ms | 2 MB + 64 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #5 | 42.27 us | 52 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #6 | 40.53 us | 52 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #7 | 40.21 us | 52 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #8 | 67.99 ms | 4 MB + 724 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #9 | 67.977 ms | 4 MB + 724 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #10 | 60.645 ms | 4 MB + 456 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #11 | 75.289 ms | 5 MB + 48 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #12 | 75.904 ms | 3 MB + 952 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #13 | 38.26 us | 52 KB | Accepted | Score: 0 | 显示更多 |
Judge Duck Online | 评测鸭在线
Server Time: 2024-04-20 02:19:20 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用