同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

1651_子集卷积

2022-5-16 18:17| 发布者: Hocassian| 查看: 45| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-2-8950479632900-Problem List-采集的数据-后羿采集器.html

Pro.ID

1651

Title

子集卷积

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=1651

AC

Submit

Ratio

0.00%

时间&空间限制

Time Limit: 50000/50000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)

描述

这是一道模板题。

给出两个集合幂级数 f , g ，求它们的不相交集合并卷积。

卷积在模 10⁹ + 9 意义下进行。

输入

第一行输入一个数 n ，表示集合的大小。

第二行有 2ⁿ 个数，描述了 f 。

第三行有 2ⁿ 个数，描述了 g 。

对于所有数据，1 ≤ n ≤ 20 , 0 ≤ f_i, g_i < 10⁹+9 。

输出

Description

这是一道模板题。

给出两个集合幂级数 f , g ，求它们的不相交集合并卷积。

卷积在模 10⁹ + 9 意义下进行。

Input

第一行输入一个数 n ，表示集合的大小。

第二行有 2ⁿ 个数，描述了 f 。

第三行有 2ⁿ 个数，描述了 g 。

对于所有数据，1 ≤ n ≤ 20 , 0 ≤ f_i, g_i < 10⁹+9 。

Output

输出一行 2ⁿ 个数，表示 f 和 g 卷积后的结果。

Sample Input

2
1 0 2 1
2 0 2 1

Sample Output

2 0 6 3

样例输入