UOJ Logo Universal Online Judge

UOJ

#442. 【集训队作业2018】观众小P

统计

小P最近迷上了石头剪刀布,他观看了一场沙雕石头剪刀布大赛

比赛共有 $2^n$ 个沙雕参加, 分为 $n$ 轮,在每轮中,第 $0$ 位选手和第 $1$ 位选手对战,胜者作为新的第 $0$ 位选手,第 $2$ 位和第 $3$ 位对战,胜者作为新的第 $1$ 位选手,以此类推。

小P得知,每个沙雕都有一种固定的偏爱决策,每个沙雕在每一次对战中都只会使用他的偏爱决策。

如果一次对战的双方的偏爱决策相同,那么这次对战就永远不会结束,那么作为观众会十分无聊。

现在,小P知道了偏爱每种决策的沙雕数目,他想知道一种能够决出最终胜负的初始的次序。

若有多种可能次序,我们设字典序最小的为答案。

因为答案可能很长,你只需要输出答案的$hash$值以及第$l$到$r$位。

$$hash=\sum_{i=0}^{2^n-1}S_i \times 233^i \bmod998244353$$

($S_i$表示初始标号为$i$的人的偏好决策对应的大写字母 ASCII 码)

输入格式

第一行两个整数$n, op$,表示数据规模和数据类型。

第二行一个大整数,表示偏爱决策为石头$R$的人数。

第三行一个大整数,表示偏爱决策为剪刀$S$的人数。

第四行一个大整数,表示偏爱决策为布$P$的人数。

若$op\neq 1$,第五,六行,两个$n$位二进制数$l,r$,表示要求你输出的范围。

输出格式

若不存在合法初始序列,输出-1,否则:

若$op\neq 2$,输出一个整数,表示最优序列$hash$值。

若$op\neq 1$,输出一个由$"R,S,P"$构成的字符串,表示最优序列的第$l$到$r$位。

样例一

input

4 3
4
4
8
0000
1111

output

-1

样例二

input

1 1
1
1
0

output

19421

样例三

input

2 2
1
2
1
01
10

output

SR

样例四

input

3 3
2
3
3
011
110

output

879001374
SPSR

样例五至样例六

见样例数据下载。

限制与约定

本题采用捆绑测试。

对于所有子任务均满足 $1\ \leq\ n\ \leq\ 300000,\ 0\leq\ r-l\leq\ 300000 ,\ R+S+P=2^n$。

子任务编号子任务分值$n$的范围$r-l$的范围数据类型
$1$3$4$$10$$3$
$2$19$20$$1000$$3$
$3$11$2000$$10000$$1$
$4$8$2000$$10000$$2$
$5$14$2000$$10000$$3$
$6$15$300000$$300000$$1$
$7$10$300000$$300000$$2$
$8$20$300000$$300000$$3$

时间限制:$\texttt{1s}$

空间限制:$\texttt{512MB}$

下载

样例数据下载