题目来源:Atcoder Beginner Contest 326--E

DQ-1 Revenge of "The Salary of AtCoder Inc."

题目大意

给定你个奖励池，第个奖励池里有元钱。你有一个面的骰子和一个记录你从哪一个奖池取出奖励的记录器(初始时，)，循环执行以下操作直至终止。

1. 扔一次骰子，点数为.
2. 和比较，如果,则取出奖池的奖励并更新，重复步骤1;否则，终止抽奖.

求最后游戏结束时你所能获得的奖金的期望

题目解析

这道题考察的知识点不难，单纯放在概率论上都是一道简单的离散型随机变量的问题。这种问题必然会遵循同样的通项公式规律，所以我们从现成的样例入手,将之想象为一个简单的高考第19题：

解：

设离散型随机变量为“游戏结束时获得的总金额”,则可取等情况。

(说明：如果最后只拿到了3元，也就是只拿到了1号奖池的东西，就要求第一次投掷的结果为1，第二次同样为1，此时不满足条件2，退出游戏。)

(说明：如果最后只拿到了3元，也就是只拿到了2号奖池的东西，就要求第一次投掷的结果为2，第二次为1或2，此时不满足条件2，退出游戏。下同理。)

(说明：如果最后只拿到了5元，也就是只拿到了1和2号奖池的东西，就要求第一次投掷的结果为1，第二次为2，第三次为1或2，此时不满足条件2，退出游戏。下同理。)

(说明：如果最后拿到了11元，也就是拿到了1和2号、3号奖池的东西，就要求第一次投掷的结果为1，第二次为2，第三次为3。其实此时不需要再投掷第四次，但是我们为了统一模式来发现后面的规律，假设扔了第四次，此时第四次无论是谁都会结束游戏，故为)

则期望为

很好，高考已经拿到了满分。

但是，这个题还没有.

观察上述的东西，我们可能会有一些发现。比如说：

eng？

这两个的概率为什么是相等的？

不确定，再看看：

我们假设有四个奖池：3，2，6，10.

惊奇，这是一种必然吗？

再深入探究一下：

哦？ 有点意思了，每一种情况的概率最终是由组成情况的奖池数和最后一个奖池的编号决定的——奖池数目决定有几个，最后一个奖池的编号决定最后一个概率为多少！

那我们是不是能够设定一个函数,表示最后一个奖池为的情况可能的部分期望，这样对求和就能得到总期望？

针对3面骰子尝试观察一下：

再针对四面骰子方程给出

有点感觉了，化简之后观察，并且确定给出了以下方程

直接用这个公式计算的话，时间复杂度将达到惊人的，面对的数据显然还是太高了。

观察发现，可以用二项式定理对函数进行化简：

其中

前缀和在输入的时候就参与预处理，在初始化时就预处理取模结果，所以求解的时间复杂度为，总算法时间复杂度为，完美通过。

对于分数求模，使用费马小定理解决：

结合快速幂解决问题。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=300001;
ll a[MAXN],sum[MAXN],invn[MAXN],invN[MAXN];
ll n;
const ll MOD=998244353;
ll quickpow(ll a,ll b)
{
    ll e=1;
    while(b)
    {
        if(b&1)e=(a*e)%MOD;
        a=(a*a)%MOD;
        b>>=1;
    }
    return e;
}
ll quickinv(ll a)
{
    return quickpow(a,MOD-2);
}
void init()
{
    sum[0]=0;
    invn[0]=invN[0]=1;
    ll _n=quickinv(n);
    for(int i=1;i<=3;i++)
    {
        invn[i]=(invn[i-1]*_n)%MOD;
    }
    ll _N=(n+1)*_n%MOD;
    for(int i=1;i<=n;i++)
    {
        invN[i]=(invN[i-1]*_N)%MOD;
        cin>>a[i];
        sum[i]=(sum[i-1]+a[i])%MOD;
    }
}
ll f(ll i)
{
    ll ans1=0,ans2=0;
    ans1=(((i*a[i])%MOD*invn[2])%MOD*invN[i-1])%MOD;
    ans2=(((i*sum[i-1])%MOD*invn[3])%MOD*invN[i-2])%MOD;
    return (ans1+ans2)%MOD;
}
int main()
{
    cin>>n;
    init();
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        ans=(ans+f(i))%MOD;
    }
    cout<<ans<<endl;
    system("pause");
    return 0;

}