期望
定义
如果 \(X\) 是离散的随机变量，输出值为 \(x_1,x_2,\cdots\)，和输出值的相应的概率为 \(p_1,p_2,\cdots\)（概率和为 \(1\)）。
则 \(E(X) = \sum_{i} p_ix_i\)
例题
Revenge of "The Salary of AtCoder Inc."
[ABC326E] Revenge of "The Salary of AtCoder Inc."
青木是 AtCoder 公司的一名员工，他本月的工资由整数 \(N\) 和长度为 \(N\) 的序列 \(A\) 决定，具体如下。
首先，给他一个\(N\)面的骰子，该骰子以相等的概率显示从\(1\)到\(N\)的整数，以及一个变量\(x=0\)。
然后，重复以下步骤直到结束。
- 掷一次骰子，让\(y\)成为结果。
- 如果是\(x\lt y\)，付给他\(A_y\)日元，让\(x=y\)。
- 否则，终止该过程。
青木这个月的工资就是通过这个过程支付的总额。
求青木本月工资的对 \(998244353\) 取模后的结果。
思路：
根据期望的线性，工资的总期望 \(E\) 等于序列 \(A\) 上的每一个值乘以 \(p(i)\)，其中 \(p(i)\) 表示骰子掷到 \(i\) 且有效的概率。
则 \(E = \sum p_ia_i\)。而
\[p_i = \frac{1}{n}\sum^{i - 1}_{j = 0} p_j \]其中 \(\frac{1}{n}p_j\) 表示在 \(j\) 这个点，掷骰子掷到 \(i\) 的概率。其中 表示在 j 这个点，掷骰子掷到 i 是一个整体。
可以用前缀和优化计算 \(O(n)\).
code:
#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
const int MAXN = 3e5 + 7;
const int MOD = 998244353;
int n;
int p[MAXN],prep[MAXN],a[MAXN];
int qpow(int a,int x){
int res = 1;
while(x){
if(x & 1) res = res * a % MOD;
a = a * a % MOD;
x >>= 1;
}
return res;
}
signed main(){
scanf("%lld", &n);
for(int i = 1;i <= n;i++) scanf("%lld", &a[i]);
p[0] = 1,prep[0] = 1;
for(int i = 1;i <= n;i++){
p[i] = prep[i - 1] * qpow(n,MOD - 2) % MOD;
prep[i] = (prep[i - 1] + p[i]) % MOD;
}
int ans = 0;
for(int i = 1;i <= n;i++){
(ans += (a[i] * p[i])) %= MOD;
}
printf("%lld", ans);
return 0;
}
Coupons
每张彩票上有一个漂亮图案，图案一共n种，如果你集齐了这n种图案就可以~~~~兑换大奖。
现在请问，在理想（平均）情况下，你买多少张彩票才能获得大奖的？
思路:
设 \(dp_i\) 为从第 \(i\) 种到 \(n\) 种所要经过的期望步数,易知 \(dp_n = 0\).
则:
\[dp_{n - 1} = \frac{1}{n} dp_n + \frac{n - 1}{n} dp_{n - 1} + 1\\ dp_{n - 2} = \frac{2}{n} dp_{n - 1} + \frac{n - 2}{n} dp_{n - 2} + 1\\ \vdots \]我们归纳化简:
\[dp_i = \frac{n - i}{n} dp_{i + 1} + \frac{i}{n} dp_{i} + 1\\ dp_i = dp_{i + 1} + \frac{n}{n - i}\\ ans = \sum^{n}_{i = 1} \frac{n}{i} \]循环统计答案即可.
我们分析过程: \(dp_{n - 1} = \frac{1}{n} dp_n + \frac{n - 1}{n} dp_{n - 1} + 1\)
\(\frac{1}{n} dp_n\) 表示有 \(\frac{1}{n}\) 的概率拿到未选择过的种类的期望,而 \(\frac{n - 1}{n}\) 的概率停在原地不动,而这两个操作都会使期望加 \(1\).
分析结束,式子成立,无代码.
收集邮票
有 \(n\) 种不同的邮票，皮皮想收集所有种类的邮票。唯一的收集方法是到同学凡凡那里购买，每次只能买一张，并且买到的邮票究竟是 \(n\) 种邮票中的哪一种是等概率的，概率均为 \(1/n\)。但是由于凡凡也很喜欢邮票，所以皮皮购买第 \(k\) 次邮票需要支付 \(k\) 元钱。
现在皮皮手中没有邮票，皮皮想知道自己得到所有种类的邮票需要花费的钱数目的期望。
首先我们设 \(f_i\) 表示从 \(i\) 种邮票收集到 \(n\) 种邮票的期望步数。
那么易知 \(f_n\) = 0，且有：
\[f_{n - 1} = \frac{1}{n} f_n + \frac{n - 1}{n} f_{n - 1} + 1 \\ f_{n - 2} = \frac{2}{n} f_{n - 1} + \frac{n - 2}{n} f_{n - 2} + 1\\ \vdots \]则 \(f_0 = \sum^{n}_{i = 1} \frac{n}{i}\)，\(f_i = f_{i + 1} + \frac{n}{n - i}\)。
但是题目中的条件是 购买第k次邮票需要支付k元钱，所以我们需要设 \(dp_i\) 为从 \(i\) 种邮票拿到 \(n\) 种的期望钱数，显然 \(dp_n = 0\)，而我们有 \(\frac{i}{n}\) 的概率取到已经取到过的，期望为 \(\frac{i}{n} (dp_i + f_i + 1)\)，有 \(\frac{n - i}{n}\) 的概率取到没有的，期望为 \(\frac{n - i}{n} (dp_{i + 1} + f_{i + 1} + 1)\)。
所以：
\[dp_i = \frac{i}{n} (dp_i + f_i + 1) + \frac{n - i}{n}(dp_{i + 1} + f_{i + 1} + 1) \]化简得到：
\[dp_i = dp_{i + 1} + 1 + f_{i + 1} + \frac{i * (1 + f_i)}{n - i} \]最后输出 dp[0] 即可。
code:
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 1e4 + 7;
int n;
double f[MAXN];
double dp[MAXN];
int main(){
scanf("%d", &n);
for(int i = n - 1;i >= 0;i--) f[i] = f[i + 1] + n * 1.0 / (n - i);
for(int i = n - 1;i >= 0;i--) dp[i] = dp[i + 1] + 1 + f[i + 1] + i * (1 + f[i]) / (n - i);
printf("%.2lf", dp[0]);
return 0;
}
代码超短。
OSU!
一共有 \(n\) 次操作，每次操作只有成功与失败之分，成功对应 \(1\)，失败对应 \(0\)，\(n\) 次操作对应为 \(1\) 个长度为 \(n\) 的 01 串。在这个串中连续的 \(X\) 个 \(1\) 可以贡献 \(X^3\) 的分数，这 \(x\) 个 \(1\) 不能被其他连续的 \(1\) 所包含（也就是极长的一串 \(1\)，具体见样例解释）
现在给出 \(n\)，以及每个操作的成功率，请你输出期望分数，输出四舍五入后保留 \(1\) 位小数。
我们考虑第 \(i\) 位和第 \(i + 1\) 位，设第 \(i\) 位为 \(1\) 产生连续的成功操作的长度的期望为 \(x\)，则分数期望为 \(x^3\)。到 \(i + 1\) 位时，长度的期望变为 \((x + 1) \times p_{i + 1}\)，分数的期望变成 \(((x + 1) \times p_{i + 1}) ^ 3 = p_{i + 1}^3 \times (x ^ 3 + 3 x ^ 2 + 3 x + 1)\)。
观察式子，我们发现我们需要知道 \(x,x^2,x^3\) 的期望。
则我们设 \(x_i,y_i,z_i\) 分别表示 \(1,2,3\) 次方的期望，则有：
\[x_i = (x_{i - 1} + 1) \times p_i \]\[y_i = (y_{i - 1} + 2x_{i - 1} + 1) \times p_i \]\[z_i = (z_{i - 1} + 3y_{i - 1} + 3x_{i - 1} + 1) \times p_i \]但是我们的答案不是单独一个点对整个序列产生分数的期望，所以要改一下三次方的式子：
\[z_i = (z_{i - 1} + 3y_{i - 1} + 3x_{i - 1} + 1) \times p_i + z_{i - 1} \times (i - p_i) \]\[z_i = z_{i - 1} + (3y_{i - 1} + 3x_{i - 1} + 1) \times p_i \]答案就是 \(z_n\)。
code:
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 1e5 + 7;
double x1[MAXN],x2[MAXN],x3[MAXN];
int n;
double p[MAXN];
int main(){
cin >> n;
for(int i = 1;i <= n;i++) cin >> p[i];
for(int i = 1;i <= n;i++) x1[i] = (x1[i - 1] + 1) * p[i];
for(int i = 1;i <= n;i++) x2[i] = (x2[i - 1] + 2 * x1[i - 1] + 1) * p[i];
for(int i = 1;i <= n;i++) x3[i] = x3[i - 1] + (3 * x2[i - 1] + 3 * x1[i - 1] + 1) * p[i];
printf("%.1lf", x3[n]);
return 0;
}