小红这天又和小紫发起了一场对战。对战的规则如下: 两人各有一些怪兽卡。每回合两人随机的从自己当前存活的怪兽卡中抽取一张发起决斗,战斗力低的怪兽卡死亡。如果两张怪兽卡战斗力相同,则无事发生。 游戏会进行到“如果抽卡,则 100% 的概率无事发生”或者“有一方卡牌被用完”时结束。请你计算小红和小紫游戏进行回合数的期望。
输入描述:
第一行输入两个正整数,分别代表小红和小紫的怪兽卡数量。第二行输入个正整数,代表小红的每张怪兽卡战斗力。第三行输入个正整数,代表小紫的每张怪兽卡战斗力。


输出描述:
一个整数,代表最终回合数期望对取模的值。可以证明,最终的答案一定是个有理数,你只需要输出其对取模的结果。分数取模的定义:假设答案是,那么其对取模的答案是找到一个整数满足且对取模等于。
示例1

输入

1 1
1
1

输出

0

说明

显然第一回合都不需要进行,因为一定会无事发生。
示例2

输入

2 3
2 2
1 1 1

输出

3

说明

一定会进行 3 回合,直到小紫的怪兽全部死亡。
示例3

输入

2 1
1 2
2

输出

2

说明

有 1/2 的概率会进行 1 回合,1/4 的概率会进行 2 回合,1/8 的概率会进行 3 回合……
最终答案是 1/2*1+1/4*2+1/8*3+……
该无穷级数收敛于 2。

加载中...