QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 1024 MB Total points: 100
[+2]
统计

时间限制:3 秒,空间限制:1024 MB。

题面描述

伊是欧最为仰慕的 OIer,因为不仅伊水平甚高,欧还常能见到伊。那段时间曾是欧最铭记的时刻,她原以为一切都会如此顺利。直到一个夏天,那天大雨,雨滴在玻璃板上噼啪作响。在这之后,一切都不复存在。欧知道伊去了哪里,但又不想知道。

后来的一天,她发现黑板上的一处未被擦除的草稿。她也终于找出先前某天的些许快乐时光:那时候欧丢给伊一个问题,是求两个三进制数的高维“卷积”。但是她忘记了具体方式,于是随口说了一个看似没有性质的按位取 mex 作为运算表。伊给出了一种做法。可是这个做法还是太特殊了。然后她直接询问了没有性质的做法。然后……她记不起来了。

那天大雨后她已经丢失了所有关于他的回忆,直到现在才找回来一些碎片。欧此时认为,当时的伊一定给出了一个更为优秀的解法,对于随机生成的运算表,因为这“没有性质”。也许只需要稍作修改……就能找回那天末尾的记忆。仅此就好。

形式化题意

题目给出一个 3×3 的运算表 op,数组下标和值域均在 [0,2]

v3(a)ba 在三进制表示下的第 b 位的数字(最低位为 0)。

对于两个数 0i,j<3n,定义 iopj 满足: v3(iopj)k=opv3(i)k,v3(j)k(0k<n)

还给出两个数组 Ai,Bi,在 [0,9] 的整数内取。对于每个 x 求: Cx=iopj=xAiBj

特别地,运算表随机生成,且每组子任务有恰好五组数据(最后一组例外,有十组)。

输入格式

前三行每行三个整数,第 i 行第 j 个数表示 opi1,j1

接下来一行一个整数 n 表示维数。

接下来一行,包含 3n 个整数,第 i 个整数表示 Ai1

接下来一行,包含 3n 个整数,第 i 个整数表示 Bi1。数字间用空格隔开。

输出格式

一行包含 3n 个整数,第 i 个整数表示 Ci1

测试样例

样例输入 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) 表示最小的不等于 ij 的非负整数
  • 子任务 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 组。