#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAXN = 2097152 + 10;
const double PI = acos(-1.0);
struct complex{
double x, y;
complex (double xx=0, double yy=0){x=xx, y=yy;}
};
complex operator + (complex a, complex b){return complex(a.x+b.x, a.y + b.y);}
complex operator - (complex a, complex b){return complex(a.x-b.x, a.y - b.y);}
complex operator * (complex a, complex b){return complex(a.x*b.x-a.y*b.y, a.x*b.y+a.y*b.x);}
complex omega[MAXN], omegaInverse[MAXN];
int place[MAXN];
inline void init(int n){
int k = 0;
while((1 << k) < n)
k++;
for(register int i=0; i<n; i++){
for(register int j=0; j<k; j++){
if(i & (1 << j))
place[i] |= (1 << (k - j - 1));
}
}
double single = 2 * PI / n;
for(register int i=0; i<n; i++){
omega[i] = complex(cos(single*i), sin(single*i));
omegaInverse[i] = complex(omega[i].x, -omega[i].y);
}
}
inline void transform(complex *a, int n, complex *omega){
for(register int i=0; i<n; i++){
if(i < place[i])
swap(a[i], a[place[i]]);
}
for(register int range=2; range <=n; range <<= 1){
int mid = range >> 1;
int k = n / range;
for(register complex *p = a; p != a + n; p += range){
for(register int i=0; i<mid; i++){
int tmp = mid + i;
complex t = omega[k * i] * p[tmp];
p[tmp] = p[i] - t;
p[i] = p[i] + t;
}
}
}
}
inline int read(){
int x = 0;
char ch = getchar();
while(ch < '0' || ch > '9')
ch = getchar();
while('0' <= ch && ch <= '9'){
x = x*10 + ch - '0';
ch = getchar();
}
return x;
}
int n1, n2;
complex c1[MAXN], c2[MAXN];
int ans[MAXN];
int main(){
n1 = read();
n2 = read();
n1++;
n2++;
int n = 1;
while(n < n1 + n2)
n <<= 1;
for(register int i=0; i<n1; i++)
c1[i].x = read();
for(register int i=0; i<n2; i++)
c2[i].x = read();
init(n);
transform(c1, n, omega);
transform(c2, n, omega);
for(register int i=0; i<n; ++i)
c1[i] = c1[i] * c2[i];
transform(c1, n, omegaInverse);
for(register int i=0; i<n1+n2-1; i++){
printf("%d ", (int)floor(c1[i].x/n + 0.5));
}
return 0;
}
Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
Subtask #1 Testcase #1 | 14.861 ms | 128 MB + 24 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #2 | 96.787 ms | 130 MB + 452 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #3 | 51.309 ms | 128 MB + 816 KB | Accepted | Score: 100 | 显示更多 |
Subtask #1 Testcase #4 | 51.304 ms | 128 MB + 804 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #5 | 15.034 ms | 128 MB + 24 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #6 | 14.266 ms | 128 MB + 24 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #7 | 14.272 ms | 128 MB + 24 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #8 | 91.333 ms | 130 MB + 184 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #9 | 92.075 ms | 130 MB + 184 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #10 | 86.347 ms | 129 MB + 940 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #11 | 97.213 ms | 130 MB + 532 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #12 | 98.42 ms | 129 MB + 412 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #13 | 14.266 ms | 128 MB + 24 KB | Accepted | Score: 0 | 显示更多 |