UOJ Logo Universal Online Judge

UOJ

#522. 【美团杯2020】版本答案

统计

酒馆战棋也是蒜斜非常喜欢的游戏。他常常一边玩游戏一边思考着哲♂学问题。众所周知,当前的酒馆战棋的版本答案是多个圣盾剧毒的峰哥。作为一名善于发问的新世纪大学生,蒜斜想要明白当双方都拥有版本答案的时候,游戏会变成什么样呢?究竟是谁杀了峰哥,而峰哥又杀了谁呢?

现在,假设在酒馆战棋的一轮战斗中,战斗的一方有 $n$ 个随从,另一方有 $m$ 个随从,所有的随从都是圣盾剧毒的峰哥,问期望多少次进攻后战斗结束。

题目补充

在这儿,我们补充介绍一下峰哥的属性以及酒馆战棋的战斗流程。峰哥的卡牌如下图所示,在本题中,血量、攻击力、费用都没有意义,你只需要留意峰哥的特殊属性。

fgnb

酒馆战棋的战斗流程为:

  1. 战斗开始前,双方的随从按照从左到右的顺序被标上了序号。如果有 $k \in \{n,m\}$ 个随从,那么第一个随从的编号为 $1$,最后一个随从的编号为 $k$。其中编号为 $i+1$ 的随从在 $i$ 之后,编号为 $1$ 的随从在 $k$ 之后。
  2. 双方轮流行动,随从多的一方先手,如果双方随从数相同,则等概率随机一方开始攻击。
  3. 当前攻击的一方的一个随从进行攻击。如果当前回合是这一方的第一个攻击回合,则编号为 $1$ 的随从攻击,否则假设上一次这一方攻击的随从编号是 $x$,这一次由 $x$ 后面第一个还活着的随从攻击。注意,当只有一个随从存活的时候,可能出现 $x$ 再次攻击的情况。
  4. 攻击的随从等概率随机挑选一个还存活的敌方随从攻击。攻击结果:无论是攻击的随从还是被攻击的随从,如果身上有圣盾,则圣盾失去;如果没有圣盾,则随从死亡。
  5. 峰哥的效果触发:对于每一个当前没有圣盾的峰哥,如果有一个和它同一方的其他随从(不包括自己)在刚才的攻击中失去了圣盾,则它获得圣盾。
  6. 如果存在一方没有任何随从存活,游戏结束。否则进入对方回合,回到步骤 $3$。

如果你对战斗流程依然不了解,你可以看这个视频。 该视频从 0:55 开始就对应本题 $n=m=6$ 的情况。

输入格式

输入三个整数 $n,m, p (1 \leq n,m \leq 2000, n+m < p \leq 10^9+7$ 且 $p$ 为质数 $)$

输出格式

输出一行一个整数,表示期望轮数对 $p$ 取模后的结果。即,如果期望轮数的最简分数表示为 $\frac{a}{b}$,你需要输出一个整数 $c$ 满足 $c \times b = a \text{ mod } p$。

样例一

input

1 1 3

output

2

样例二

input

1 2 5

output

2

限制与约定

Small Task: $n+m\leq 5$。

Large Task: $n,m \leq 2000$。

时间限制:$2\texttt{s}$

空间限制:$512\texttt{MB}$

下载

样例数据下载