概率期望训练
前言
因为本人概率期望方面知识的不足，导致比赛经常被期望题腐乳，同时也为了减轻队内数学手的压力，遂开此题单。希望能在网络赛之前写完30道以上吧。
选用了洛谷的xzy的概率期望题单
链接
P5104 红包发红包
容易推出第\(k\)个人的抢到的期望钱数为\(\frac {w}{{2}^{k}}\)
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9 + 7;
int power(int a, int b) {
int res = 1;
while (b) {
if (b & 1ll) res = res * a % mod;
b >>= 1;
a = a * a % mod;
}
return res;
}
void solve() {
int w, n, k;
cin >> w >> n >> k;
cout << w * power(power(2, k), mod - 2) % mod << "\n";
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t;
t = 1;
//std::cin >> t;
while (t--) {
solve();
}
return 0;
}
P6154 游走
要求所有路径长度的期望，假设所有路径的长度为\(S\)，以及所有路径的个数为\(T\)，已得所求的期望为\(\frac {S}{T}\)。因此，问题的关键点在于怎样求出\(S,T\)，注意到是有向无环图，拓扑排序后跑\(dp\)即可
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
int power(int a, int b) {
int res = 1;
while (b) {
if (b & 1ll) res = res * a % mod;
b >>= 1;
a = a * a % mod;
}
return res;
}
void solve() {
int n, m;
cin >> n >> m;
vector<vector<int>> g(n + 1);
vector<int> deg(n + 1);
for (int i = 1; i <= m; i ++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
deg[v] ++;
}
auto in = deg;
queue<int> q;
vector<int> len(n + 1), cnt(n + 1);
for (int i = 1; i <= n; i ++) {
cnt[i] = 1;
if (!deg[i]) {
q.push(i);
}
}
while (q.size()) {
int t = q.front();
q.pop();
for (auto v : g[t]) {
--deg[v];
cnt[v] = cnt[t] + cnt[v], cnt[v] %= mod;
len[v] = len[v] + len[t] + cnt[t], len[v] %= mod;
if (!deg[v]) q.push(v);
}
}
int f = 0, d = 0;
for (int i = 1; i <= n; i ++) {
f += len[i], f %= mod;
d += cnt[i], d %= mod;
}
cout << f * power(d, mod - 2) % mod;
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t;
t = 1;
//std::cin >> t;
while (t--) {
solve();
}
return 0;
}
SP1026 FAVDICE - Favorite Dice
令\({dp}_{i}\)表示，已经投出了\(i\)面，投出\(n\)面的期望次数，所以\({dp}_{n}\)为\(0\)，答案为\({dp}_{0}\)，所以为逆推
因为已经选了\(i\)个数，再选一个与已经选过的数不同的概率是\(\frac {n - i}{n}\)，相同为\(\frac {i}{n}\)
于是可得\({f}_{i}=\frac {n-i}{n}{f}_{i+1}+\frac {i}{n}{f}_{i}+1\)
解的\({f}_{i}={f}_{i+1}+\frac {n}{n - i}\)
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n;
cin >> n;
//dp[i]表示当前已经有了i面被投到，还需要多少次使得n面被投到
vector<double> dp(n + 1);
dp[n] = 0;
for (int i = n - 1; i >= 0; i --) {
dp[i] = dp[i + 1] + 1.0 * n / (n - i);
}
cout << fixed << ' ' << setprecision(10) << dp[0] << "\n";
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t;
t = 1;
std::cin >> t;
while (t--) {
solve();
}
return 0;
}
P1297 [国家集训队] 单选错位
根据期望的线性性，可以单独考虑每一个题做对的期望
- 所有可能的结果，共\({a}_{i} \times {a}_{i - 1}\)种
- 做对的结果，共\(min({a}_{i},{a}_{i-1})\)种
所以做对第\(i\)题的概率为\({p}_{i}=\frac {min({a}_{i}, {a}_{i - 1})}{{a}_{i-1}\times {a}_{i}}=\frac {1}{max({a}_{i - 1}, {a}_{i})}\)
最后答案为\(\sum {p}_{i}\)
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n;
cin >> n;
int A, B, C;
cin >> A >> B >> C;
vector<int> a(n + 1);
cin >> a[1];
for (int i = 2; i <= n; i ++) {
a[i] = (a[i - 1] * A + B) % 100000001;
}
for (int i = 1; i <= n; i ++) {
a[i] = a[i] % C + 1;
}
a[0] = a[n];
double ans = 0;
for (int i = 1; i <= n; i ++) {
ans += 1.0 / max(a[i - 1], a[i]);
}
cout << fixed << setprecision(3) << ans << "\n";
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t;
t = 1;
// std::cin >> t;
while (t--) {
solve();
}
return 0;
}