问题 28508 --抛硬币

28508: 抛硬币

时间限制: 1 Sec  内存限制: 128 MB
提交: 1  解决: 1
[提交][状态][讨论版][数据上传:][下载FPS0元][下载测试数据0元][6kb]

题目描述

有一枚硬币,抛出正面H的概率为a/b,抛出反面T的概率为1-a/b。现在TT小朋友开始玩丢硬币的游戏,并且把每次抛出的结果记录下来,正面记为H,反面记为T,于是她得到了一个抛硬币序列HTHHT…。她突然想到一个问题:在抛出正面和反面概率都是1/2的情况下,要使得抛出的序列出现目标序列HT,期望要抛多少次。然而经过1秒的思考以后她发现,若第一次抛出的是T,那么还需要期望抛出HT的次数,如果第一次抛出的是H,则期望只需要抛出T的次数,而期望抛出T的次数显然是2。她设抛出HT的期望次数是x,则得到了方程:

x=1+(1/2*x+1/2*2) 

解得x=4,所以抛出HT的期望次数是4次。

她在解决了这个弱化很多的问题以后,开始思考对于一般情况下,抛出正反面的概率不一定相同,且抛出的目标序列不一定为HT时需要的期望步数。然而经过很长一段时间的苦思冥想仍然无果,于是她开始求助于你。

输入输出格式

输入格式:


第一行两个数a,b。意义如题目描述。

接下来1行一个只包含’H’和’T’的字符串S。表示要抛出的目标序列。


输出格式:


输出仅一行p/q,其中p和q均为正整数且互质,表示抛出目标序列S所需要的期望步数。

注意,若q为1时,不省略/1。


输入输出样例

输入样例#1: 复制
1 2
HT
输出样例#1: 复制
4/1

说明

50%数据a=1,b=2,|s|<=20 100%数据a=b,b=100,|s|<=1000

输入

输出

提示

来源

[提交][状态]