← 返回题目列表

AtCoder · agc044_c

C. 奇怪的舞蹈

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

分数: 1000 点

问题陈述

有 3^N 人们围成圈跳舞。 我们用 0,1,\dots, 3^{N}-1 圆中的位置,从任意位置开始,顺时针旋转。最初,圆圈中的每个位置都由一个人占据。

人们将跳两种歌曲:萨尔萨舞和伦巴舞。

  • 当演奏萨尔萨舞曲时,处于该位置的人 i 转到位置 j,其中 j 是替换所有数字得到的数字 1 与 2 和所有数字 2 与 1 阅读时 i 在基地 3 (例如,处于该位置的人 46 转到位置 65).
  • 当演奏伦巴时,在该位置的人 i 移动到位置 i+1 (带有标识 3^N = 0).

给你一个字符串 T=T_1T_2\cdots T_{|T|} 这样 T_i=S 如果 i-th 歌曲是萨尔萨舞曲并且 T_i=R 如果是伦巴舞。 所有歌曲播放完后,最初就位的人 i 就位 P_i。 计算数组 P_0,P_1,\dots, P_{3^N-1}.

约束

  • 1 \le N \le 12
  • 1 \le |T| \le 200,000
  • T 仅包含字符 S 和 R.

输入

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

N
T

输出

您应该在标准输出上打印:

P_0 P_1 \cdots P_{3^N-1}

示例输入 1

1
SRS

示例输出 1

2 0 1 

在播放任何歌曲之前,位置为: 0, 1, 2.

当我们说“人 i”,我们的意思是“最初处于位置的人 i".

  1. 在第一个萨尔萨舞之后,位置是: 0, 2, 1.
  2. 伦巴舞结束后,位置是: 1, 0, 2 (所以,人 0 就位 1, 人 1 就位 0 和人 2 就位 2).
  3. 第二个萨尔萨舞之后,位置是 2, 0, 1 (所以,人 0 就位 2, 人 1 就位 0 和人 2 就位 1).

示例输入 2

2
RRSRSSSSR

示例输出 2

3 8 1 0 5 7 6 2 4 

示例输入 3

3
SRSRRSRRRSRRRR

示例输出 3

23 9 22 8 3 7 20 24 19 5 18 4 17 12 16 2 6 1 14 0 13 26 21 25 11 15 10