概率期望杂记 25.7.29始

期望概率的手记

我真的是概率困难户······

\(\textbf{0.1}\) 洛谷P5104 红包发红包

这个抢红包系统是这样的：假如现在有 \(w\) 元，那么你抢红包能抢到的钱就是 \([0,w]\) 等概率均匀随机出的一个实数 \(x\)。

现在红包发了一个 \(W\) 元的红包，有 \(n\) 个人来抢。那么请问第 \(k\) 个人期望抢到多少钱？

输出答案对 \(10^9+7\) 取模后的结果。

显然期望每个人抢到的钱为 \(\dfrac{w}{2}\)，所以第 \(k\) 个人抢到 \(\dfrac{W}{2^k}\) 的钱。

\(\huge \mathscr{Code}\)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 1e9+7;
int n,m,k;
int qpow(int a,int b){if(b==1) return a%MOD;int s = qpow(a,b/2);return b&1?s*s%MOD*a%MOD:s*s%MOD;
}
signed main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>m>>k;cout<<n%MOD*qpow(qpow(2,k),MOD-2)%MOD;return 0;
}

\(\textbf{0.2}\) 洛谷P1850 [NOIP 2016 提高组] 换教室

对于刚上大学的牛牛来说，他面临的第一个问题是如何根据实际情况申请合适的课程。

在可以选择的课程中，有 \(2n\) 节课程安排在 \(n\) 个时间段上。在第 \(i\)（\(1 \leq i \leq n\)）个时间段上，两节内容相同的课程同时在不同的地点进行，其中，牛牛预先被安排在教室 \(c_i\) 上课，而另一节课程在教室 \(d_i\) 进行。

在不提交任何申请的情况下，学生们需要按时间段的顺序依次完成所有的 \(n\) 节安排好的课程。如果学生想更换第 \(i\) 节课程的教室，则需要提出申请。若申请通过，学生就可以在第 \(i\) 个时间段去教室 \(d_i\) 上课，否则仍然在教室 \(c_i\) 上课。

由于更换教室的需求太多，申请不一定能获得通过。通过计算，牛牛发现申请更换第 \(i\) 节课程的教室时，申请被通过的概率是一个已知的实数 \(k_i\)，并且对于不同课程的申请，被通过的概率是互相独立的。

学校规定，所有的申请只能在学期开始前一次性提交，并且每个人只能选择至多 \(m\) 节课程进行申请。这意味着牛牛必须一次性决定是否申请更换每节课的教室，而不能根据某些课程的申请结果来决定其他课程是否申请；牛牛可以申请自己最希望更换教室的 \(m\) 门课程，也可以不用完这 \(m\) 个申请的机会，甚至可以一门课程都不申请。

因为不同的课程可能会被安排在不同的教室进行，所以牛牛需要利用课间时间从一间教室赶到另一间教室。

牛牛所在的大学有 \(v\) 个教室，有 \(e\) 条道路。每条道路连接两间教室，并且是可以双向通行的。由于道路的长度和拥堵程度不同，通过不同的道路耗费的体力可能会有所不同。 当第 \(i\)（\(1 \leq i \leq n-1\)）节课结束后，牛牛就会从这节课的教室出发，选择一条耗费体力最少的路径前往下一节课的教室。

现在牛牛想知道，申请哪几门课程可以使他因在教室间移动耗费的体力值的总和的期望值最小，请你帮他求出这个最小值。

语文神题。

我们令 \(dp\) 方程 \(dp_{i,j,k}\) 表示上了第 \(i\) 门课，到目前为止申请了 \(j\) 门，当前是否申请 \(0 \textbf{ or } 1\)。

我们可以用 \(\textbf{Floyd}\) 算法求出两两教室间的最短路，设为 \(g[i][j]\)。

于是有转移方程：

\[dp[i][j][0] = \min \begin{cases} dp[i-1][j][0] + g[c[i-1]][c[i]] \\ dp[i-1][j][1] + g[c[i-1]][c[i]] \times (1-k[i]) + g[d[i-1]][c[i]] \times k[i] \end{cases} \]

\[dp[i][j][1] = \min \begin{cases} dp[i-1][j-1][0] + g[c[i-1]][c[i]] \times (1-k[i]) + g[c[i-1]][d[i]] \times k[i] \\ dp[i-1][j-1][1] + g[d[i-1]][d[i]] \times k[i-1] \times k[i] + g[d[i-1]][c[i]] \times k[i-1] \times (1-k[i]) + g[c[i-1]][d[i]] \times (1-k[i-1]) \times k[i] + g[c[i-1]][c[i]] \times (1-k[i-1]) \times (1-k[i]) \end{cases} \]

\(\huge \mathscr{Code}\)

#include<bits/stdc++.h>
using namespace std;
const int N = 2e3 + 100;
const double INF = 1e17 + 5;
int n, m, v, e, c[N], d[N];
double k[N], dp[N][N][2];
int g[N][N];
int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);memset(g, 0x3f, sizeof(g));cin >> n >> m >> v >> e;for (int i = 1; i <= n; i++) cin >> c[i];for (int i = 1; i <= n; i++) cin >> d[i];for (int i = 1; i <= n; i++) cin >> k[i];for (int i = 1; i <= e; i++) {int a, b, w;cin >> a >> b >> w;g[a][b] = g[b][a] = min(g[a][b], w);}for (int k = 1; k <= v; k++) {for (int i = 1; i <= v; i++) {for (int j = 1; j <= v; j++) {g[i][j] = min(g[i][j], g[i][k] + g[k][j]);}}}for (int i = 1; i <= v; i++) g[i][i] = 0;for (int i = 0; i <= n; i++) {for (int j = 0; j <= m; j++) {dp[i][j][0] = dp[i][j][1] = INF;}}dp[1][0][0] = dp[1][1][1] = 0;for (int i = 2; i <= n; i++) {dp[i][0][0] = dp[i - 1][0][0] + g[c[i - 1]][c[i]];for (int j = 1; j <= min(i, m); j++) {int Case1 = c[i - 1], Case2 = d[i - 1], Case3 = c[i], Case4 = d[i];dp[i][j][0] = min({ dp[i][j][0],dp[i - 1][j][0] + g[Case1][Case3],dp[i - 1][j][1] + g[Case1][Case3] * (1 - k[i - 1]) + g[Case2][Case3] * k[i - 1] });dp[i][j][1] = min({ dp[i][j][1],dp[i - 1][j - 1][0] + g[Case1][Case3] * (1 - k[i]) + g[Case1][Case4] * k[i] });dp[i][j][1] = min({ dp[i][j][1],dp[i - 1][j - 1][1] + g[Case2][Case4] * k[i] * k[i - 1] + g[Case2][Case3] * k[i - 1] * (1 - k[i]) + g[Case1][Case4] * (1 - k[i - 1]) * k[i] + g[Case1][Case3] * (1 - k[i - 1]) * (1 - k[i]) });}}double ans = INF;for (int i = 0; i <= m; i++) ans = min({ ans,dp[n][i][0],dp[n][i][1] });cout << fixed << setprecision(2) << ans;return 0;
}

\(\textbf{0.3}\) 洛谷P5249 [LnOI2019] 加特林轮盘赌

加特林轮盘赌是一个养生游戏。

与俄罗斯轮盘赌等手枪的赌博不同的是，加特林轮盘赌的赌具是加特林。

加特林轮盘赌的规则很简单：在加特林的部分弹夹中填充子弹。游戏的参加者坐在一个圆桌上，轮流把加特林对着自己的头，扣动扳机一秒钟。中枪的自动退出，坚持到最后的就是胜利者。

我们使用的是 2019 年最新技术的加特林，他的特点是无需预热、子弹无限，每一个人，在每一回合，中枪的概率是完全相同的 \(P_0\)。

每局游戏共有 \(n\) 只长脖子鹿，从 1 长脖子鹿开始，按照编号顺序从小到大进行游戏，绕着圆桌不断循环。

游戏可能会循环进行多轮，直到场上仅剩下最后一只长脖子鹿时，游戏结束。

给出 \(P_0\) 和 \(n\)，询问 \(k\) 号长脖子鹿最终成为唯一幸存者的概率 \(P_k\)。

如果 \(P_0=0\)，我们认为胜者为 \(1\) 号。

考虑 \(F_{i,j}\) 表示在 \(i\) 个人的情况下存活下来的概率。

很显然，因为只能活一个人。

\[\sum_{i=1}^{n} F_{n,i} = 1 \]

我们可以得知，当一个人崩自己时候，有 \(p\) 的概率崩死自己。

相当于所有人全部向前走了一步，并少了一个人。

\[F_{i,j} \to F_{i-1,j-1} \]

但是 \(1-p\) 的概率没崩死自己。

相当于所有人向前走了一步。

\[F_{i,j} \to F_{i,j-1} \]

于是有一个优雅的转移方程：

\[F_{i,j} = p \times F_{i-1,j-1} + (1-p) \times F_{i,j-1} \]

但是初始状态我们并不知道，即 \(F_{i,1}\) 的情况。

\(F_{1,1} = 1\)，显然。

注意到转移方程可以贡献 \(n-1\) 个方程，加上开头提出的公式。

\(n\) 元一次方程，简单解出。

\(\huge \mathscr{Code}\)

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 100;
double p, dp[2][N];
int n, k, last, cur = 1;
int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> p >> n >> k;if (p == 0) {if (k == 1) cout << 1;else cout << 0;return 0;}dp[1][1] = 1;for (int i = 2; i <= n; i++) {last = cur, cur ^= 1;double basea = 1, basec = 0, A = 0, C = 0;for (int j = 2; j <= i; j++) {basea *= 1 - p;A += basea;basec = (1 - p) * basec + p * dp[last][j - 1];C += basec;}dp[cur][1] = (1 - C) / (A + 1);for (int j = 2; j <= i; j++) {dp[cur][j] = p * dp[last][j - 1] + (1 - p) * dp[cur][j - 1];}}cout << fixed << setprecision(10) << dp[cur][k];return 0;
}