提交记录 5321
提交时间 |
评测时间 |
2018-08-17 11:01:07 |
2020-08-01 00:15:37 |
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
const int N=4e5+5,p=998244353;
int n,m,L,inv,a[N],b[N],R[N];
inline int pow(int x,int y){
int ans=1;while(y){if(y&1)ans=1ll*ans*x%p;x=1ll*x*x%p;y>>=1;}
return ans;
}
void FFT(int *A,int o){
for(int i=0;i<n;++i)if(R[i]>i)swap(A[R[i]],A[i]);
for(int i=1;i<n;i<<=1){
int wn=pow(3,(p-1)/(i<<1)),a,b,w;
for(int j=0;j<n;j+=(i<<1)){
w=1;for(int k=0;k<i;++k,w=1ll*w*wn%p){
a=A[j+k],b=1ll*A[i+j+k]*w%p;
A[j+k]=(a+b)%p;A[i+j+k]=(a-b+p)%p;
}
}
}
if(o==-1){
reverse(A+1,A+n);
for(int i=0;i<n;++i)A[i]=1ll*A[i]*inv%p;
}
}
int main(){
ios::sync_with_stdio(false);
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;for(n=1;n<=m;n<<=1)++L;inv=pow(n,p-2);
for(int i=1;i<n;++i)R[i]=((i&1)<<(L-1))|(R[i>>1]>>1);
FFT(a,1);FFT(b,1);for(int i=0;i<n;++i)a[i]=1ll*a[i]*b[i]%p;
FFT(a,-1);
for(int i=0;i<=m;++i)cout<<a[i]<<' ';
cout<<endl;return 0;
}
Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
Subtask #1 Testcase #1 | 42.93 us | 72 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #2 | 67.624 ms | 4 MB + 508 KB | Accepted | Score: 100 | 显示更多 |
Subtask #1 Testcase #3 | 31.378 ms | 1 MB + 872 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #4 | 31.357 ms | 1 MB + 860 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #5 | 43.95 us | 72 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #6 | 43.17 us | 72 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #7 | 42.68 us | 72 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #8 | 63.167 ms | 4 MB + 240 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #9 | 63.212 ms | 4 MB + 240 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #10 | 58.716 ms | 3 MB + 996 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #11 | 67.83 ms | 4 MB + 588 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #12 | 64.365 ms | 3 MB + 468 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #13 | 41.71 us | 72 KB | Accepted | Score: 0 | 显示更多 |
Judge Duck Online | 评测鸭在线
Server Time: 2024-03-29 01:03:03 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用