P15105

乘法表问题

难度 5 级 小学 动态规划入门 区间DP
讨论 统计 38通过 61提交 62.3%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

给定a、b和c的乘法规则如表1。第1行第2列为b表示a \times b = b,第2行第1列为c表示b \times a = c。

对于任意给定的字符串,通过加括号,可以得到一个表达式。比如x=bbbba,可以加括号为(b(bb))(ba),则根据乘法表得到a。 现在给定一个字符串x,试问有多少种加括号的方式,可以最终得到a。

输入

输入为一行只含有a、b和c的字符串。字符串长度不超过40.

输出

输出得到a的加括号的不同方式数目。

样例

样例 1
输入
bbbba
输出
6

来源

动规专题

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交