Public Judge

pjudge

Time Limit: 1 s Memory Limit: 512 MB Total points: 125 Hackable ✓
统计

题目描述

给定正整数 $n$。给出一个 $n\times 2\times 2$ 的 01 数组 $A_{i,j,k}$,其中 $i\in [0,n-1],j\in [0,1],k\in [0,1]$。

定义一种二元运算 $f(x,y)\ (0\le x,y < 2^n,x,y\in \mathbb{Z})$ 的值为:

  • 设 $x=\sum_{i=0}^{n-1}2^ia_i$,其中 $a_i\in \{0,1\}$。
  • 设 $y=\sum_{i=0}^{n-1}2^ib_i$,其中 $b_i\in \{0,1\}$。
  • 设 $z=\sum_{i=0}^{n-1}2^iA_{i,a_i,b_i}$。
  • 则 $f(x,y)=z$。

给出两个长为 $2^n$ 的数组 $p,q$(下标均为 $[0,2^n-1]$),计算它们下标做 $f$ 运算的卷积。换句话说,请求出数组 $res$(下标为 $[0,2^n-1]$),其中 $res_i=\sum_{j=0}^{2^n-1}\sum_{k=0}^{2^n-1} [f(j,k)=i]p_iq_j$。

输入格式

第一行一个正整数 $n$。

第二行包含 $n$ 个长度为 $4$ 的 01 串。第 $i$ 个 01 串从前往后表示 $A_{i-1,0,0},A_{i-1,0,1},A_{i-1,1,0},A_{i-1,1,1}$ 的值。

第三行 $2^n$ 个整数,描述数组 $p$。第四行 $2^n$ 个整数,描述数组 $q$。

输出格式

输出一行以空格隔开的 $2^n$ 个整数,描述数组 $res$。

样例数据

样例 1 输入

3
0111 0110 0001
0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0

样例 1 输出

0 0 0 0 0 0 0 1

样例 2 输入

2
1100 1101
2 0 2 1
2 0 2 1

样例 2 输出

2 4 3 16

样例 3 输入

1
0000
142857142 857142857
998244353 1755646

样例 3 输出

999999998000000001 0

样例 4

见下发文件中的 ex_conv4.in/ex_conv4.ans。该样例满足子任务 1 的限制。

样例 5

见下发文件中的 ex_conv5.in/ex_conv5.ans。该样例满足子任务 5 的限制。

子任务

请注意,本题的满分为 125 分。

对于所有数据:保证 $n\le 18,0\le p_i\le 10^9,0\le q_i\le 10^9,\sum p_i\le 10^9,\sum q_i\le 10^9$。

  • 子任务 1($1$ 分)$n\le 10$。
  • 子任务 2($1$ 分)每个 01 串都是 0001
  • 子任务 3($4$ 分)每个 01 串都是 0110
  • 子任务 4($5$ 分)每个 01 串都是 00010111
  • 子任务 5($114$ 分)无特殊限制。

Hack

Hack 功能在本题中可用。