Java教程

数学期望 DP

本文主要是介绍数学期望 DP,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

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

也就是:

\(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\)(这样不会出现在原地打转的情况,比较符合拓扑序,方便入手),那么应该怎么算。
显然,

\[dp_i = \cfrac{dp_{i+1}+dp_{i+2}+...+dp_{i+a_i}}{a_i} + 1 \]

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

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

\[dp_i = \cfrac{dp_i+dp_{i+1}+dp_{i+2}+...+dp_{i+a_i}}{a_i+1}+1 \]

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

\[\cfrac{a_i}{a_i+1} dp_i=\cfrac{dp_{i+1}+dp_{i+2}+...+dp_{i+a_i}}{a_i+1} + 1 \]

那么,

\[dp_i=\cfrac{a_i+1}{a_i} (\cfrac{dp_{i+1}+dp_{i+2}+...+dp_{i+a_i}}{a_i+1} + 1) \\ =\cfrac{dp_{i+1}+dp_{i+2}+...+dp_{i+a_i}+a_i+1}{a_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;
}
这篇关于数学期望 DP的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!