← 返回题目列表

AtCoder · arc132_f

F. 高桥最强

中文机器翻译题面 查看原题

分数: 900 点

问题陈述

高桥、青木和 Snuke 将与 k 石头剪刀布。

让我们调用一个长度为 k 组成 P, R, S a 策略。游戏进行如下。

  • 每个参与者选择一个策略。
  • 播放 k 石头剪刀布。在 i第轮,每个参与者玩对应的手牌 i所选策略中的第一个字符:论文 P,摇滚 R和剪刀 S.

青木会从策略中随机选择一种 n 策略 a_1,\dots,a_n 具有相同的概率。 Snuke 会从策略中随机选择一种 m 策略 b_1,\dots,b_m 具有相同的概率。 他们的选择是相互独立的。

高桥会很高兴,如果他是 仅有的 至少其中一项的获胜者 k 回合。 对于每个 3^k 可能的策略,找到他在选择该策略时变得快乐的概率,并将其乘以打印 nm 为整数(可以证明这个值是整数)。

注释

在三人石头剪刀布的游戏中,以下三种情况使高桥成为唯一的胜利者。

  • 高桥玩纸,而青木和斯努克玩石头。
  • 高桥玩石头,青木和斯努克玩剪刀。
  • 高桥玩剪刀,青木和斯努克玩布。

约束

  • 1 \leq k \leq 12
  • 1 \leq n,m \leq 3^k
  • 每个 a_i 和 b_i 是一个长度为的字符串 k 组成 P, R, S.
  • a_1,\dots,a_n 是不同的。
  • b_1,\dots,b_m 是不同的。

输入

输入由标准输入按以下格式给出:

k n m
a_1
\vdots
a_n
b_1
\vdots
b_m

输出

打印 3^k 值。的 i-th 值应该是高桥选择时的答案 i- 按字典顺序排列的最小可能策略。


示例输入 1

2 1 3
RS
RP
RR
RS

示例输出 1

3
3
3
0
1
0
0
1
0

青木选择策略 RS.

如果 Snuke 选择策略 RP,能够满足高桥目标的策略是 PP, PR, PS.

如果 Snuke 选择策略 RR,能够满足高桥目标的策略是 PP, PR, PS.

如果 Snuke 选择策略 RS,能够满足高桥目标的策略是 PP, PR, PS, RR, SR.

因此,高桥选择的概率 分别为 PP, PR, PS, RP, RR, RS, SP, SR, SS 是 1, 1, 1, 0, \frac 13, 0, 0, \frac 13, 0。 打印它们乘以 3.


示例输入 2

3 5 4
RRP
SSS
RSR
PPP
RSS
PPS
SRP
SSP
RRS

示例输出 2

4
7
7
6
9
10
4
7
8
4
8
7
4
8
8
3
7
7
3
7
6
4
8
8
1
5
5