Problem 3F. Rotate Circle
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
Problem 3F. Rotate Circle
时间限制:2s
空间限制:256MB
Description
\(n\) 个人站成一圈,每个人都按顺时针方向或逆时针方向看向他前面的人。
但是,他们互相都不想看着对方,也就是说如果两个人面对对方,所有这些互相面对的相邻的人都会转过身来。所有动作都是瞬间同时发生的。
我们将使用字符 "A" 表示顺时针方向站着的人,使用字符 "B" 表示逆时针方向站着的人。然后,由字母 "A" 和 "B" 组成的字符串将表示人们站成的圈,记录从第一个人开始按顺时针方向进行。
例如一个字符串 "ABBBABBBA" 的圆在一秒后变成 "BABBBABBA" ,一个 "BABBA" 的圆变成 "ABABB" 。
上图(见vijos)说明了圆 "BABBA" 如何转变为 "ABABB" 。
当前人们站立状态由字符串 \(s\) 描述。您的任务是确定在一秒钟前经过变换能变为 \(s\) 的可能状态的数量。如果有一个人在一种状态下面对顺时针方向,而在另一种状态下面对逆时针方向,那么这两种状态就被认为是不同的。
Input Format
输入一行一个字符串 \(s\) ,仅由字母 "A" 和 "B" 组成。
Output Format
输出一行一个整数,表示所求的状态数。
Input Example #1:
BABBBABBA
Output Example #1:
2
Input Example #2:
ABABB
Output Example #2:
2
Input Example #3:
ABABAB
Output Example #3:
4
Data Range
对于 50% 的数据,保证 \(3 \le len_s \le 10\) ;
对于全部测试数据,保证 \(3 \le len_s \le 1000\) 。
Bote
在第一个样例中,可能的初始状态是 "ABBBABBAB" 和 "ABBBABBBA" 。
在第二个样例中,可能的初始状态是 "AABBB" 和 "BABBA" 。