当前位置：首页 > news >正文

数学期望专题

news 2025/7/5 20:53:53

9.29 - 10.6 更新时间约持续一周

优惠券 Coupons

题目链接：优惠券 Coupons

假设我们某个情况下，我们已经有了 k 种图案，在这个条件下，获得一个新图案需要 $t_k$ 天，那我们要求的就是 $\sum_{k = 0}^{n - 1}E(t_k)$ 。由于已经有了 k 种图案，那么获得一个新图案的概率就是 $\frac{n - k}{n}$ ，那么期望天数 $E(t_k) = \frac{n}{n - k}$ ，最终答案就是 $\sum_{k = 0}^{n - 1}E(t_k) = \sum_{k = 0}^{n - 1}\frac{n}{n - k} = \sum_{i = 1}^{n} \frac{n}{i}$

要注意一下分数时候的输出格式。

~~另外就是这道题我刚开始给卡常了，有点ex。~~

#include <bits/stdc++.h>
using namespace std;#define int long longint n, x, y;int gcd(int a, int b) { return a == 0 ? b : gcd(b % a, a); }signed main() {while (scanf("%lld", &n) != EOF) {x = n, y = 1;for (int i = 2; i <= n; i++) {x = x * i + y * n, y *= i;int GCD = gcd(x, y);x /= GCD, y /= GCD;}if (x % y == 0) printf("%lld\n", x / y);else {int a = x / y;x %= y;int lena = log10(a) + 1, leny = log10(y) + 1;for (int i = 0; i <= lena; i++) printf(" ");printf("%lld\n%lld ", x, a);for (int i = 1; i <= leny; i++) printf("-");puts("");for (int i = 0; i <= lena; i++) printf(" ");printf("%lld\n", y);}}return 0;
}

Sugar Sweet II

题目链接：2023ICPC区域赛杭州站H题

当 $a[i] < a[b[i]]$ 的时候，无论 a[b[i]] 是否更新，即无论事件以什么顺序发生，a[i] 一定会被更新，则第 i 个孩子手上的糖的期望为 a[i] + w[i]。
当 $a[i] \ge a[b[i]] + w[b[i]]$ 的时候，无论 a[b[i]] 是否更新，即无论事件以什么顺序发生，a[i] 一定无法更新，则第 i 个孩子手上的糖的期望为 a[i]。
除去以上两种情况，a[i] 是否更新取决于 a[b[i]] 是否更新。对于这种情况，我们可以以 (b[i], i) 建一张有向图，记录一个 dis 表示该节点更新前有多少个节点需要更新，第一种情况的 dis 记为 1，第二种情况的 dis 记为 0，通过 dfs 遍历得到每一个节点的 dis。每一个节点可以更新的概率就是 $\frac{1}{dis!}$ ，因为只需要这 dis 个节点以这一种特定顺序排列就可以保证该节点被更新。期望就是 $\frac{1}{dis!} (a[i] + w[i]) + (1 - \frac{1}{dis!})a[i] = a[i] + \frac{w[i]}{dis!}$ ，最后要求乘法逆元。

对于 $\frac{x}{y}\equiv ans(mod \hspace{0.5em}p)$ 即 $\frac{ans}{x} \cdot y \equiv 1 (mod \hspace{0.5em} p)$ 的乘法逆元，根据费马小定理，当 a 和 p 互质的时候，有 $a^{p - 1} \equiv 1 (mod \hspace{0.5em} p)$ ，则 $\frac{ans}{x} = y ^{p - 2} \hspace{0.2em} \% \hspace{0.2em} p$ 即 $ans = x \cdot y ^{p - 2} \hspace{0.2em} \% \hspace{0.2em} p$ 。

#include <bits/stdc++.h>
using namespace std;#define int long longconst int N = 5e5 + 10, mod = 1e9 + 7;
int a[N], b[N], w[N], fac[N], dis[N], head[N], num = 0;
struct edge { int to, nxt; } e[N];inline int read() {int x = 0, f = 1; char c = getchar();while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();return x * f;
}void addEdge(int u, int v) { e[++num] = (edge){v, head[u]}, head[u] = num; }int qpow(int x, int k) {int res = 1LL;while (k) {if (k & 1) res = res * x % mod;x = x * x % mod;k >>= 1;}return res;
}void dfs(int u) {for (int i = head[u], v; i; i = e[i].nxt) {v = e[i].to;dis[v] = dis[u] + 1;dfs(v);}
}signed main() {fac[0] = 1;for (int i = 1; i < N; i++) fac[i] = fac[i - 1] * i % mod;int t = read();while (t--) {int n = read();for (int i = 1; i <= num; i++) e[i] = {0, 0};num = 0;for (int i = 1; i <= n; i++) a[i] = read(), dis[i] = 0;for (int i = 1; i <= n; i++) b[i] = read(), head[i] = 0;for (int i = 1; i <= n; i++) w[i] = read();for (int i = 1; i <= n; i++) {if (a[i] < a[b[i]]) dis[i] = 1;else if (a[i] >= a[b[i]] + w[b[i]]) dis[i] = 0;else addEdge(b[i], i);}for (int i = 1; i <= n; i++) if (dis[i] == 1) dfs(i);for (int i = 1; i <= n; i++) {if (dis[i] == 0) printf("%lld ", a[i]);else printf("%lld ", (a[i] + w[i] * qpow(fac[dis[i]], mod - 2) % mod) % mod);}puts("");}return 0;
}

查看全文

http://www.mrgr.cn/news/39629.html