快速傅里叶变换

快速傅里叶变换

Description

请计算

\[C[k]=\sum_{k\le i<n}(a[i]*b[i-k])\] 。

有 \(n < = 10^5\),a,b中的元素均为小于等于100的非负整数。

Input

第一行一个整数\(N\),接下来\(N\)行,第\(i+2..i+N-1\)行,每行两个数,依次表示\(a[i],b[i]\) (\(0 \le i < N\))。

Output

输出\(N\)行,每行一个整数,第\(i\)行输出\(C[i-1]\)。

Sample Input

5
3 1
2 4
1 1
2 4
1 4

Sample Output

24
12
10
6
1

Source

BZOJ

信息

难度
7
分类
FFT 点击显示
标签
递交数
21
已通过
6
通过率
29%
上传者