#include <cmath>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <limits>
#include <map>
#include <vector>
#include <queue>
#define LL int
#define ft first
#define sd second
#define mp(x,y) make_pair(x,y)
#define db double
//#define int LL
using namespace std;
const int N = 1<<21;
const int mod = 1004535809;
const int INF =numeric_limits<int >::max();
const db Pi=acos(-1.);
#define rep(i,x,y) for (int i=x;i<=y;++i)
#define rr(i,x,y) for (int i=x;i<y;++i)
void read(int &x)
{
x=0;
char ch=getchar();
int f=1;
while (!isdigit(ch)) (ch=='-'?f=-1:0),ch=getchar();
while ( isdigit(ch)) x=x*10+ch-'0',ch=getchar();
x*=f;
}
int n,m,A[N],B[N];
int C[N];
int qsm(int a,int b)
{
int tmp=1;
while (b)
{
if (b&1) tmp=1ll*tmp*a%mod;
a=1ll*a*a%mod;
b>>=1;
}
return tmp;
}
int rev[N*4];
const int yg=3;
void NTT(int *a,int n,int f)
{
rr(i,0,n) if (i>rev[i]) swap(a[i],a[rev[i]]);
for (int i=1;i<n;i<<=1)
{
int wn=qsm(yg,(mod-1)/(i<<1)),x,y;
for (int j=0;j<n;j+=(i<<1))
{
for (int w=1,k=0;k<i;++k,w=1ll*wn*w%mod)
{
x=a[j+k];
y=1ll*a[i+j+k]*w%mod;
a[j+k]=(x+y)%mod;
a[i+j+k]=(x-y+mod)%mod;
}
}
}
if (f==1) return;
reverse(a+1,a+n);
int inv=qsm(n,mod-2);
rr(i,0,n) a[i]=1ll*a[i]*inv%mod;
}
void cal(int *a,int * b,int n,int m,int *c)
{
int R=n+m,L=1,g=0;
for (;L<=R;L<<=1,++g);
rr(i,0,L) rev[i]=(rev[i>>1]>>1) | ((i&1)<<g-1);
NTT(A,L,1);NTT(B,L,1);
rr(i,0,L) C[i]=1ll*A[i]*B[i]%mod;
NTT(C,L,-1);
}
signed main()
{
///freopen("data.txt","r",stdin);
//freopen("Moon.txt","w" ,stdout);
read(n);read(m);
rep(i,0,n) read(A[i]);
rep(i,0,m) read(B[i]);
cal(A,B,n,m,C);
n+=m;
rep(i,0,n) printf("%d ",C[i]);
return 0;
}
Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
Subtask #1 Testcase #1 | 8.86 us | 28 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #2 | 73.896 ms | 5 MB + 456 KB | Accepted | Score: 100 | 显示更多 |
Subtask #1 Testcase #3 | 33.967 ms | 2 MB + 308 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #4 | 33.973 ms | 2 MB + 296 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #5 | 9.67 us | 28 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #6 | 10.13 us | 28 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #7 | 8.47 us | 28 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #8 | 68.841 ms | 5 MB + 188 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #9 | 68.665 ms | 5 MB + 188 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #10 | 63.479 ms | 4 MB + 944 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #11 | 74.16 ms | 5 MB + 536 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #12 | 74.487 ms | 4 MB + 416 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #13 | 7.78 us | 28 KB | Accepted | Score: 0 | 显示更多 |