#P18407. Bocchi the Rock
Bocchi the Rock
Bocchi the Rock
圆周上有 个不同的点,它们把圆周分成 条弧。每个点可以染成红色或蓝色,每条弧可以染成黄色或粉色。
你可以在同色的两个点之间添加弦,不能连接一红一蓝的两个点。任意两条弦不能相交,且每个点至多连接一条弦。添加这些弦后,圆内部被划分为若干区域。
若可以添加一些满足要求的弦,使得到的每个区域都为单色,则称该着色为好着色。这里,区域“单色”是指它不同时包含黄色弧和粉色弧,只比较其圆周弧的颜色。
有些点和弧的颜色已经指定。求符合这些指定颜色的好着色数量,答案对 取模。数的是颜色的补全方式,不是添加弦的方式;同一着色有多种合法连弦方法时只计一次。输入位置区分各点和弧。
输入格式
第一行包含整数 ,满足 。
第二行包含长度为 的字符串 ,沿圆周按弧、点、弧、点的顺序记录颜色:
- 对奇数 , 只可能为
Y、P、?,表示第 条弧是黄色、粉色,或者颜色尚未确定。 - 对偶数 , 只可能为
R、B、?,表示第 个点是红色、蓝色,或者颜色尚未确定。
首尾相接:最后一个点之后是第一条弧。? 只能在该位置允许的两种颜色中选择。
输出格式
输出一行一个整数,表示符合已知颜色约束的好着色数量,对 取模后的值。
样例 1
2
????
12
样例 2
3
??YR?B
4
样例 3
5
YBYRPBYRYB
0
样例说明
样例 1 的十二种好着色分别为:YBYB、YBYR、YRYB、YRYR、PBPB、PBPR、PRPB、PRPR、YBPB、YRPR、PBYB、PRYR。
下图为样例 2 的原题示意图。左图是颜色尚未补全时的圆;中图的 PBYRYB 是好着色,可以连接两个蓝点得到单色区域;右图的 PBYRPB 不是好着色。
