#P4773. 红鲤鱼与绿鲤鱼

    ID: 3725 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,B,分别表示有多少条红鲤鱼和绿鲤鱼。

输出格式

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

1 1
499122454
1 2
45

提示

10pts:1A+B510 pts: 1 \leqslant A + B \leqslant 5 30pts:1A+B2030 pts: 1 \leqslant A + B \leqslant 20 70pts:1A+B300070 pts: 1 \leqslant A + B \leqslant 3000 $$100 pts: 1 \leqslant A \leqslant 1e18, 1 \leqslant B \leqslant 1e7 $$

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

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

样例1: 有两种可能:

  1. AC WA AC
  2. WA AC AC

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

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

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