时间限制:3 秒,空间限制:1024 MB。
题面描述
伊是欧最为仰慕的 OIer,因为不仅伊水平甚高,欧还常能见到伊。那段时间曾是欧最铭记的时刻,她原以为一切都会如此顺利。直到一个夏天,那天大雨,雨滴在玻璃板上噼啪作响。在这之后,一切都不复存在。欧知道伊去了哪里,但又不想知道。
后来的一天,她发现黑板上的一处未被擦除的草稿。她也终于找出先前某天的些许快乐时光:那时候欧丢给伊一个问题,是求两个三进制数的高维“卷积”。但是她忘记了具体方式,于是随口说了一个看似没有性质的按位取 mex 作为运算表。伊给出了一种做法。可是这个做法还是太特殊了。然后她直接询问了没有性质的做法。然后……她记不起来了。
那天大雨后她已经丢失了所有关于他的回忆,直到现在才找回来一些碎片。欧此时认为,当时的伊一定给出了一个更为优秀的解法,对于随机生成的运算表,因为这“没有性质”。也许只需要稍作修改……就能找回那天末尾的记忆。仅此就好。
形式化题意
题目给出一个 3×3 的运算表 op,数组下标和值域均在 [0,2]。
记 v3(a)b 为 a 在三进制表示下的第 b 位的数字(最低位为 0)。
对于两个数 0≤i,j<3n,定义 iopj 满足: v3(iopj)k=opv3(i)k,v3(j)k(0≤k<n)
还给出两个数组 Ai,Bi,在 [0,9] 的整数内取。对于每个 x 求: Cx=∑iopj=xAiBj
特别地,运算表随机生成,且每组子任务有恰好五组数据(最后一组例外,有十组)。
输入格式
前三行每行三个整数,第 i 行第 j 个数表示 opi−1,j−1。
接下来一行一个整数 n 表示维数。
接下来一行,包含 3n 个整数,第 i 个整数表示 Ai−1。
接下来一行,包含 3n 个整数,第 i 个整数表示 Bi−1。数字间用空格隔开。
输出格式
一行包含 3n 个整数,第 i 个整数表示 Ci−1。
测试样例
样例输入 1
1 2 1 1 2 0 2 1 0 1 5 7 8 9 8 4
样例输出 1
60 192 168
样例输入 2
0 0 1 0 2 0 2 2 1 2 8 1 1 8 1 3 2 5 3 9 0 6 3 5 3 4 9 6
样例输出 2
358 213 97 190 84 106 209 78 105
样例 1 和 2 只满足子任务 5 的性质并使用其数据生成器生成。样例 3 至样例 8 分别对应除子任务 5 以外的其他子任务,并使用和该子任务测试数据一样的数据生成器生成。
数据范围
- 子任务 1(5 分):opi,j=(i+j)mod
- 子任务 2(5 分):\text{op}_{i, j} = \text{mex}(i, j),\text{mex}(i, j) 表示最小的不等于 i 或 j 的非负整数
- 子任务 3(20 分):\text{op}_{i, j} \in \{0, 1\},且任意两行,每一位要么全部相同,要么全部不同
- 子任务 4(30 分):\text{op}_{i, j} \in \{0, 1\}
- 子任务 5(10 分):n \le 9
- 子任务 6(10 分):n = 10,依赖子任务 5
- 子任务 7(20 分):n = 11,依赖子任务 6
对于 100\% 的数据,保证 1 \le n \le 11,\text{op}_{i, j} 在子任务要求下均匀随机地从所有可能方案中选择一种。保证 0 \le A_i, B_i \le 10 且为整数。除最后一组外每组子任务恰有 5 组数据,最后一组子任务有 10 组。