#P4773. 红鲤鱼与绿鲤鱼

    ID: 3736 Type: RemoteJudge 400ms 32MiB Tried: 0 Accepted: 0 Difficulty: 5 Uploaded By: Tags>数学高精度最大公约数,gcd

红鲤鱼与绿鲤鱼

题目背景

JerryC 家里除了有驴之外,还有一个有着红鲤鱼和绿鲤鱼的鱼缸。

题目描述

在 JerryC 家里的鱼缸里,有一些红鲤鱼和绿鲤鱼(鱼缸里没有驴!)。这天晚上 23:05 的时候,JerryC 闲的无聊,于是打开了某神秘 OJ 开始爆肝。

作为一名膜%法师,JerryC 可以通过预言术得知下一次自己的提交是对是错。当然,预言术使用的工具就是眼前的鱼缸了。每当 JerryC 的预言术指示一只红鲤鱼的时候,就说明这次提交会 WA,同时会增加 5min 的罚时;如果是绿鲤鱼就会 AC。(当然,由于 JerryC 的膜%法,JerryC 是不会番薯田扛把子的。JerryC 第一次提交会在第 5min,而且不幸的是 JerryC 的膜%法有 5min 的冷却时间)并且 JerryC 在每一次预言后就会把预言到的那一只鲤鱼取出来,以便比赛完毕后给鱼缸换水(给自己换换口味)。

现在 JerryC 告诉你他家里有多少条红鲤鱼和绿鲤鱼,请你告诉他他这场比赛的罚时期望是多少。当然,JerryC 会按顺序做题,并且罚时只会记录 AC 的题目,算罚时的时候需要加上 AC 的时间,并且所有的鲤鱼用完后还会提交一次,而且这一次 JerryC 并不会预测并且必定 AC。

由于 JerryC 脾气比较犟,所以他不会因为 WA 掉一道题而换一道题去做,除非 AC。

输入格式

一行,两个正整数 A,BA, B,分别表示有多少条红鲤鱼和绿鲤鱼。

输出格式

一行,一个正整数,表示罚时的期望模 998244853998244853 的结果。如果结果除不尽时,若结果可以表示为 PQ\frac{P}{Q},则需要输出 P×Qmod2modmodP \times Q^{mod-2} \bmod mod

1 1
499122454
1 2
45

提示

样例解释 #1

有两种可能:

  1. AC WA AC;
  2. WA AC AC。

第一个情况的罚时是 55(第 5 分钟 AC) ⁣+ 5\!+ \ 5(WA 一次罚时 5 分钟) ⁣+ 15\!+ \ 15(第 15 分钟 AC)=25= 25

第二个情况的罚时是 55(WA 一次罚时 5 分钟) ⁣+ 10\!+ \ 10(第 10 分钟 AC) ⁣+ 15\!+ \ 15(第 15 分钟 AC )=30=30

所以期望罚时为 25+302=552 \frac{25+30}{2} = \frac{55}{2} 需要对分数取模,所以最后答案为 499122454499122454

数据规模与约定

  • 10 pts:1A+B51 \le A + B \le 5
  • 30 pts:1A+B201 \le A + B \le 20
  • 70 pts:1A+B30001 \le A + B \le 3000
  • 100 pts:1A10181 \le A \le 10 ^ {18}1B1071 \le B \le 10 ^ 7

最后六个点时限 2400ms,其他点时限 400ms。

温馨提示:注意模数\color{white}{\text{温馨提示:注意模数}}