对于一组离散型随机变量，出现其中某一变量的概率乘以这一变量值，再求和，就是数学期望。

也就是：

\(E=∑\limits_{i=1}^n(p_i×v_i)\)
通过这个定义，我们可以感知到，所谓期望，其实表示的是一组离散型随机变量的平均水平。 也可认为是进行某件事能得到的平均结果，或者理想代价。所以它也可以叫做一组离散型随机变量的均值。这也是期望这个概念的实际意义。

关于期望的一些性质：

\(E(X+Y)=E(X)+E(Y)\)
\(E(XY)=E(X)E(Y)\)
\(E(aX+b)=aE(X)+b\)
\(E(c)=c\)
其中，当\(E(XY)=E(X)E(Y)\)的成立条件是X,Y相互独立。

以上是高中数学内容。在此重新提一下。

进行期望DP的时候，这些性质有时显得至关重要，可以帮助我们理解很多递推的转移。

ABC263E

题意：

有 \(n\) 个格子，在第 \(1 \sim n-1\) 个格子上，第 \(i\) 个格子上有一个骰子，面值为 \(0 \sim a_i\)，投一次骰子，这些面值均匀出现。投到几，就往前走几格。

从 \(1\) 号格子出发，求到 \(n\) 号格子所要投的骰子个数的数学期望。

分析：

对于线性期望 DP，通常有两种 DP 方式：

1. \(dp_i\) 表示从起始状态到 \(i\) 状态的数学期望。
2. \(dp_i\) 表示从 \(i\) 状态到起始状态的数学期望。

转移的时候，第一种方式通常从前往后转，需要起始状态已知。第二种方式通常是从后往前转，需要终止状态已知。有的时候这两种方式可以互换，有的时候不可以，需要灵活使用。

本题先考虑使用第 \(2\) 种方式，因为我们知道一个点可以前往哪些点，比较方便。
设 \(dp_i\) 表示从 \(i\) 节点开始，到达 \(n\) 的数学期望。

先从有穷条件入手，即如果骰子可以投到 \(1 \sim a_i\)（这样不会出现在原地打转的情况，比较符合拓扑序，方便入手），那么应该怎么算。
显然，

（投到 \(1,2,...,a_i\) 每一种情况的概率是 \(\frac{1}{a_i}\)；不论什么情况从 \(i\) 都要多投 \(1\) 粒骰子）

如果是原题的无穷条件呢？在这时，虽然有些情况需要投掷的骰子数量会趋于无穷，但这时的概率成指数型增长。数学期望依然收敛。怎么计算呢？
照算不误。（by ajh 大佬）

把 \(dp_i\) 提到左边有：

那么，

时间复杂度 \(O(n \log \bmod)\)，使用后缀和优化。

考虑证明。考虑 \(dp_i=\cfrac{\sum \limits_{j=1}^{a_i} dp_j} {a_i} + X + 1\)，其中 \(X\) 为（待填坑）

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f(i, a, b) for(int i = (a); i <= (b); i++)
#define cl(i, n) i.clear(),i.resize(n);
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int inf = 1000000;
const int mod = 998244353;
int a[200010];
int dp[200010];
int suf[200010];
int qpow(int x, int k){
    int ans = 1;
    while(k) {
        if(k&1)ans=ans*x%mod;
        x=x*x%mod;
        k>>=1;
    }
    return ans;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    //think twice,code once.
    //think once,debug forever.
    int n; cin >> n;
    f(i ,1,n)cin>>a[i];
    dp[n] = 0;
    for(int i = n-1;i >= 1; i--){
        int up = ((suf[i+1]-suf[i+a[i]+1])+a[i]+1+inf*mod) % mod;
        int down = a[i];
        dp[i] = up * qpow(down, mod - 2) % mod;
        suf[i] = (suf[i+1]+dp[i])%mod;
    }
    cout << dp[1] << endl;
    return 0;
}