子集卷积 ### 题目描述 给定两个长度为 $2^n$ 的数组 $a,b$，请你求出数组 $c$ 满足 ： $$ c_k=\sum_{\substack{{i \& j=0}\\{i~\mid~ j=k}}} a_i b_j $$ ### 输入描述 输入第一行仅包含一个正整数 $n$，表示数组 $a,b$ 的长度。 第二行有 $2^n$ 个数，表示数组 $a_1,a_2,\cdots,a_{2^n}$ 。 第三行有 $2^n$ 个数，表示数组 $b_1,b_2,\cdots,b_{2^n}$ 。 $1\leq n \leq 20, 0\leq a_i,b_i\leq 10^9+9$ 。 ### 输出描述 输出 $2^n$ 个数，表示 $c_1,c_2,\cdots,c_{2^n}$。由于答案可能很大，请对 $10^9+9$ 取模。 ### 输入输出样例 #### 示例 1 >输入 ```txt 2 1 2 3 5 6 7 8 9 ``` >输出 ```txt 6 19 26 76 ```