AT_fft_c.高速フーリエ変換

本题为讲座用题目，页面下方附有题解。

AtCoder 食堂正在考虑定食的菜单。

• 主菜中，价格为 $i$ 日元的有 $A_i$ 种类（$1 \leq i \leq N$）。
• 副菜中，价格为 $i$ 日元的有 $B_i$ 种类（$1 \leq i \leq N$）。

定食由一种主菜和一种副菜组成。定食的价格为所选主菜和副菜价格之和。

请计算对于每个 $k\ (1 \leq k \leq 2N)$，价格为 $k$ 日元的定食有多少种。

输入以以下格式从标准输入读入。

$N$
$A_1\ B_1$
$A_2\ B_2$
$\vdots$
$A_N\ B_N$

• 第 $1$ 行包含一个整数 $N\ (1 \leq N \leq 100,\!000)$。
• 接下来的 $N$ 行，第 $i$ 行包含两个整数 $A_i,\ B_i\ (0 \leq A_i,\ B_i \leq 100)$。

请输出 $2N$ 行。第 $k$ 行输出价格为 $k$ 日元的定食种类数。

题解

高速傅里叶变换 by AtCoder Inc.

样例解释 1

• 价格为 $1$ 日元的组合不存在。
• 价格为 $2$ 日元的组合，由于 $1$ 日元的主菜和副菜各有 $1$ 种，所以有 $1$ 种组合。
• 价格为 $3$ 日元的组合有 $1 \times 2 + 2 \times 1 = 4$ 种。

由 ChatGPT 4.1 翻译