首页 > 掷硬币

掷硬币

互联网 2021-10-26 20:35:51

掷硬币Time Limit:1000MS  Memory Limit:32768K

Description:月光闲来无事常常在掷硬币,以至于每次要做什么事的时候都要等掷硬币掷成的序列出现某一个他心中所想的序列才肯罢休。而有时候他会因为这耽误大事,所以他想计算出他心中的序列平均的情况下要掷多少次才会出现。H(HEAD)表示出现正面,T(TAIL)表示反面,则如果他心中所想是HH,则他第一次可能掷成H或T,第二次掷后出现HHHTTTTH四种情况,而HH是符合要求,如果他掷到的是TH则下次他掷出的是H而使序列成为THH,这也是符合的。而如果掷的是THT则等于要从头来过了。经过长年的研究他终于找出计算期望掷的次数的方法。首先,对于串s,正整数i定义p(si)为s的长为i的前缀定义q(si)为s的长为i的后缀设最低位为第0低位,则每个长n的串的期望对应于一个n+1位的二进制数如果p(si)等于q(si)则这个二进制数的第i低位上就为1,另外所有位为0。例如串THT对应于4位的二进制数p(s3)=q(s3)p(s1)=q(s1)则期望为二进制数(1010) 。

Input:先一行中有一个每个字符为H或T的字符串,串长小于100000 Output:每组数据输出一个整数这个整数为结果模10007 Sample Input:HTT Sample Output:42 Source:DK Status  Submit

免责声明:非本网注明原创的信息,皆为程序自动获取互联网,目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责;如此页面有侵犯到您的权益,请给站长发送邮件,并提供相关证明(版权证明、身份证正反面、侵权链接),站长将在收到邮件12小时内删除。