题解 P4773 【红鲤鱼与绿鲤鱼】

b2019dy · 2018-07-19 09:15:42 · 题解

本题是个数学题，情况总数为重排列数，即\dfrac{(a+b)!}{a!b!}
由题意可得，无论哪种情况，总会用完所有鲤鱼，则红鲤鱼的罚时必定会全部累加，最后也必定为1次AC，则罚时总值为5\dfrac{(a+b)!}{a!b!}(2a+b+1)
我们来考虑前面的绿鲤鱼，我们可以知道，绿鲤鱼记录的时间之与它所处的位置有关，证明可得，绿鲤鱼在每一个位置上的次数是相同的。次数为\dfrac{b}{a+b}\dfrac{(a+b)!}{a!b!}次。
则我们可以利用高斯公式求出等差数列，再加上之前算出的罚时，即可求出最终罚时总值。5\dfrac{b}{a+b}\dfrac{(a+b)!}{a!b!}\dfrac{(1+a+b)(a+b)}{2}+5\dfrac{(a+b)!}{a!b!}(2a+b+1)
除以情况数，并约分得期望值为5(\dfrac{(1+a+b)b}{2}+2a+b+1)
可得分母只有2这一种情况，预处理2的取模情况即可。

#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstring>
using namespace std;
long long ans,a,b;
const long long p=499122427;
int main()
{
    scanf("%lld%lld",&a,&b);
    ans=(5*((4*(a%998244853))%998244853+(2*(b%998244853))%998244853+2+(b%998244853)*(1+(a%998244853)+(b%998244853))))%998244853;
    if(ans%2==0)
    {
        printf("%lld",ans/2);
    }
    else printf("%lld",(ans*p)%998244853);
}