概率期望
Contents
模型
例1 几何分布
题意
一次伯努利试验的成功概率为 $p$，那么期望试验多次才能获得第一次成功？
答案是 $\frac{1}{p}$。
证明：设 $E[X]$ 为期望试验次数。
用 $X_i = 1$ 表示第 $i$ 次试验成功（$0$ 反之），讨论：第一次试验要么成功，要么失败：
$$E[X] = p * 1 + (1-p) * (1 + E[X|X_1=0]) = p + (1-p)(1 + E[X])$$
得到 $E[X] = \frac{1}{p}$。
例2 抽卡问题
题意
卡池里有 $N$ 种卡，每种有无限张，每次抽卡会等概率抽取一张卡，问期望多少次抽到所有种类的卡？
$N = 1$ 的情况：期望为 $1$。
$N = 2$ 的情况：先抽一张，获得一种。接下来是一个几何分布问题：有 $\frac{1}{2}$ 的概率抽到第二种卡，期望 $2$ 次即可抽到，所以总期望为 $1+2=3$。
那么在 $N$ 的情况下，设事件 $X_i$ 为：已经抽到了 $i$ 种卡，可以发现每次都是一个几何分布问题，根据 $i$ 的值决定试验成功率。
$$E[X] = E[X_1|X_0] + E[X_2|X_1] + E[X_3|X_2] + … + E[X_N|X_{N-1}]$$
其中，$E[X_k|X_{k-1}]$ 代表卡池里 $N$ 种卡已经抽到了 ${k-1}$ 种，还有 $N-k+1$ 种卡没抽到，每次试验成功率（抽到新卡）为 $\frac{N-k+1}{N}$，故期望值
$$E[X_k|X_{k-1}] = \frac{N}{N-k+1}$$
综上：
$$E[X] = \sum_{k=1}^N \frac{N}{N-k+1} = \sum_{k=1}^N \frac{N}{k}$$
例题
例1 洛谷P1850 [NOIP2016 提高组] 换教室
题意
有 $n$ 个时间段，每个时间段有 $2$ 节课程。其中在时间段 $i$ 的两节课，分别在教室 $c_i, d_i$ 上。
对于所有的时间段 $i$，牛牛预先被安排在 $c_i$ 上课。
对于一个时间段 $i$，牛牛可以申请转到教室 $d_i$ 上课。但这个申请只有 $k_i$ 的概率被批准。
牛牛最多可以申请 $m$ 个时间段，但是所有申请必须一次性提交。
同时，校园可以看作是一个图，教室为节点（共 $v$ 个教室），教室之间有双向边（共 $e$ 个边），边有长度。
每当一节课结束后，牛牛会沿着最短路径走到下一节课所在的教室。
现在牛牛想知道，怎么申请时间段，使得他在教室间移动的路程长度期望值最小，求出这个最小期望。
其中，$1 \leq n \leq 2000, 0 \leq m \leq 2000, 1 \leq v \leq 300, 0 \leq e \leq 90000$。
题解
首先用 floyd $O(n^3)$ 求出每两个节点之间的最短路长度。
然后一个很明显的 DP 思路：
设 $dp[i][j][k]$ 为：当前考虑第 $i$ 个时间段，还剩下 $j$ 次申请机会，$k=0/1$ 代表当前在哪个教室。
这个思路看起来很有道理，但是不正确。因为题目提到 所有申请必须一次性提交。
而 $k=0/1$ 如果代表当前在哪个教室，就说明我们已经知道了当前的申请结果，来考虑后面的时间段是否申请。这会导致我们的决策更加的精明，从而使得答案小于正确答案。
正确的状态为：$dp[i][j][k]$：当前考虑第 $i$ 个时间段，还剩下 $j$ 次申请机会，$k=0/1$ 代表当前 是否申请过，$dp$ 数组的值代表路径长度期望值。
然后转移的时候，就要分类讨论 是否申请下一个时间段，得到两个结果，取 $\min$ 就得到了当前状态的答案。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2002;
int n,m,v,e, c[maxn], d[maxn];
double k[maxn];
int adj[302][302], dis[302][302];
double dp[maxn][maxn][2];
// K = 1: 已申请， K = 0: 未申请
double dfs(int i, int j, int K) {
if (i >= n) return 0.0;
if (dp[i][j][K] >= 0.0) return dp[i][j][K];
double r1 = 1e18, r2 = 1e18;
// next: 申请/不申请
if (K) {
r1 = k[i] * (dfs(i+1, j, 0) + dis[d[i]][c[i+1]]) + (1.0 - k[i]) * (dfs(i+1, j, 0) + dis[c[i]][c[i+1]]);
if (j > 0)
r2 = k[i] * (k[i+1] * (dfs(i+1, j-1, 1) + dis[d[i]][d[i+1]]) + (1.0 - k[i+1]) * (dfs(i+1, j-1, 1) + dis[d[i]][c[i+1]]))
+ (1.0 - k[i]) * (k[i+1] * (dfs(i+1, j-1, 1) + dis[c[i]][d[i+1]]) + (1.0 - k[i+1]) * (dfs(i+1, j-1, 1) + dis[c[i]][c[i+1]]));
} else {
r1 = 1.0 * (dfs(i+1, j, 0) + dis[c[i]][c[i+1]]);
if (j > 0) r2 = k[i+1] * (dfs(i+1, j-1, 1) + dis[c[i]][d[i+1]]) + (1.0 - k[i+1]) * (dfs(i+1, j-1, 1) + dis[c[i]][c[i+1]]);
}
return dp[i][j][K] = min(r1, r2);
}
int main() {
scanf("%d%d%d%d",&n,&m,&v,&e);
for (int i = 1; i <= n; i++) scanf("%d", &c[i]);
for (int i = 1; i <= n; i++) scanf("%d", &d[i]);
for (int i = 1; i <= n; i++) scanf("%lf", &k[i]);
for (int i = 1; i <= e; i++) {
int u,v,w; scanf("%d%d%d",&u,&v,&w);
if (adj[u][v]) {
if (adj[u][v] > w) adj[u][v] = adj[v][u] = w;
} else adj[u][v] = adj[v][u] = w;
}
memset(dis, 0x3f3f3f3f, sizeof(dis));
for (int i = 1; i <= v; i++) {
for (int j = 1; j <= v; j++) {
if (adj[i][j])
dis[i][j] = dis[j][i] = adj[i][j];
}
}
for (int i = 1; i <= v; i++) dis[i][i] = 0;
for (int k = 1; k <= v; k++) {
for (int i = 1; i <= v; i++) {
for (int j = 1; j <= v; j++) {
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
dp[i][j][0] = dp[i][j][1] = -1;
}
}
double ans1 = 1.0 * dfs(1, m, 0), ans2 = 1e18;
if (m > 0) {
ans2 = 1.0 * dfs(1, m-1, 1);
}
double ans = min(ans1, ans2);
printf("%.2lf\n", ans);
}
例2 洛谷P3830 [SHOI2012]随机树
题意
给定一棵二叉树，初始状态下只有根节点。每次操作会在所有叶子节点中，等概率选择一个，给它添加左右两个child。
给定正整数 $n$，求：对于由此生成的含有 $n$ 个叶子节点的二叉树，输出 叶子结点深度 的期望值，和 树深度 的期望值。
其中，$n \leq 100$，根节点的深度为 $0$。
题解
先考虑一下 叶子结点深度 的期望值。
每次扩展一个叶子，设其原深度为 $x$，相当于总深度增加了 $2(x+1) - x = x+2$。
所以设，对于 $n$ 个叶子的树，平均叶子深度若为 $f_n$，则总深度为 $f_n * n$。
所以在这个树中选择一个叶子展开，平均叶子增加深度为 $f_n + 2$。
所以 $f_{n+1} = \frac{(f_n * n + f_n + 2)}{n+1} = f_n + \frac{2}{n+1}$。
然后看第二问，树深度 的期望值。
在做到这里的时候我的想法出现了一些偏差：我一直在考虑如何将 叶子数为 $(n-1)$ 的状态转移到 叶子数为 $n$ 的状态。
但是实际做法是一个很神奇的想法：
使用 左，右子树 进行转移。
设 $dp[i][j]$ 为：有 $i$ 个叶子节点，深度 $\geq j$ 的概率，枚举 左子树 叶子节点数量 $k$，有以下转移：
$$dp[i][j] = \frac{\sum\limits_{k=1}^{i-1}dp[k][j-1] + dp[i-k][j-1] - dp[k][j-1] * dp[i-k][j-1]}{i-1}$$
什么意思呢？我们先看分子：
显然对于根节点来说，它左右子树必然不为空，所以转移的时候 $k=1$ 开始，到 $(i-1)$，能转移的状态是深度为 $j-1$ 的，所以都加上。
但是因为两边深度均为 $j-1$ 算重了，所以用容斥减去重复的部分 $dp[k][j-1] * dp[i-k][j-1]$。
分子 $(i-1)$ 是哪里来的呢？因为考虑到期望的定义是 值 乘上 概率 之和。对于 $k$ 不同的情况，有不同的概率。
但是我们可以得出结论，每一种概率都是相同的。
意思就是：对于一棵 $n$ 个叶子节点的树，左子树拥有的叶子节点数量为 $1,2,…,n-1$，发生的概率均相同。
证明：用数学归纳法即可。
首先可以得到对于 $n=2$ 是相同的。
我们设 $p[i][j]$ 为：叶子节点数为 $i$ 的树中，左子树有 $j$ 个叶子节点的概率。
则 $p[i][j] = p[i-1][j-1] * \frac{j-1}{i-1} + p[i-1][j] * \frac{(i-1)-j}{i-1}$
由数学归纳法，设对于 $(i-1)$ 而言，$\forall j \in [1,i-2], p[i-1][j] = \frac{1}{i-2}$。
则 $p[i][j] = \frac{1}{i-2} * \frac{j-1}{i-1} + \frac{1}{i-2} * \frac{(i-1)-j}{i-1} = \frac{1}{i-1}$，与 $j$ 无关。
代码
#include <bits/stdc++.h>
using namespace std;
int q,n;
double dp[102][102]; // dp[i][j]: 对于第i步，深度为j的期望叶子节点期望个数
int main() {
scanf("%d%d",&q,&n);
double ans = 0.0;
if (q == 1) {
dp[1][0] = 1.0;
// 第 i 步有 2i-1 个节点, 有 i 个叶子节点
for (int i = 1; i <= n-1; i++) {
for (int j = 0; j <= i-1; j++) {
double p = dp[i][j] / (i);
dp[i+1][j+1] += p * 2.0;
dp[i+1][j] -= p * 1.0;
}
for (int j = 0; j <= i-1; j++) dp[i+1][j] += dp[i][j];
}
for (int j = 0; j <= n; j++) ans += dp[n][j] * j;
printf("%.6f\n", ans/(n));
} else {
for (int i = 0; i <= n; i++) dp[i][0] = 1.0;
dp[0][0] = 1.0;
dp[1][0] = 1.0;
dp[2][0] = dp[2][1] = 1.0;
for (int i = 3; i <= n; i++) {
for (int j = 1; j < i; j++) {
for (int k = 1; k <= i-1; k++) {
dp[i][j] += dp[k][j-1] + dp[i-k][j-1] - dp[k][j-1] * dp[i-k][j-1];
}
dp[i][j] /= (i-1);
}
}
for (int j = n-1; j >= 0; j--) {
double p = - dp[n][j+1] + dp[n][j];
ans += (p * j);
}
printf("%.6f\n", ans);
}
}
例3 洛谷 P2221 [HAOI2012]高速公路
题意
一条线上有 $n$ 个收费站，从第 $i$ 个到第 $(i+1)$ 个收费站之间有一条路，通过一条路需要交费。初始状态下，每条路的费用为 $0$。
给定 $m$ 个询问，每个询问为两种之一：
$C ~ l ~ r ~ v$：将第 $l$ 到第 $r$ 个收费站之间的所有道路费用增加 $v$。
$Q ~ l ~ r$：回答在第 $l$ 到第 $r$ 个收费站之间，等概率选择两个不同的收费站 $a,b$，从 $a$ 行驶到 $b$ 的期望费用？
其中，$1 \leq n,m \leq 10^5, -10^4 \leq v \leq 10^4$，在任何时间段，任何一条道路的费用绝对值不超过 $10^4$。
题解
线段树。首先把收费站转成道路，就对于所有的 $l,r$，都改成 $l,r-1$。对于线段树，从 $1$ 和 $n-1$ 之间build。
计算期望的时候，可以知道分母是 $C_{r-l}^2$。分子是从 $l,r$ 之间所有的选择之和。
现在问题是：如何求出一个区间内，所有可能的 $l,r$ 组合的区间和的和？
数学表达：对于区间 $[L,R]$，求
$$\sum\limits_{i=L}^R\sum\limits_{j=i}^R sum(arr[i…j])$$
直接从线段树的角度来考虑：一个区间的 $\sum\limits_{i=l}^r\sum\limits_{j=i}^r sum(arr[i…j])$，能否用左右区间的这个信息来维护？
可以的，注意到：对于一个区间 $[L,R]$ 来说，所有 $l,r$ 的组合可以分为三种：
- $l,r \in [L, mid]$
- $l,r \in [mid+1, R]$
- $l \in [L, mid], r \in [mid+1, R]$
前两种已经被子区间用到了，只要考虑第三种情况即可。
所以问题就转化成：
对于一个区间 $[L,R]$，求
$$\sum\limits_{i=L}^{mid}\sum\limits_{j=mid+1}^R sum(arr[i…j])$$
对于这个问题，我们可以固定 $l,r$ 其中之一。
比如我们固定 $l=mid$，那么 $r$ 会从 $mid+1$ 一直iterate到 $R$，得到的 sum 就是：
$$sum(arr[mid…mid+1]) + sum(arr[mid…mid+2]) + … + sum(arr[mid…R])$$
把它从 $mid$ 的位置拆开来，就等于：
$$(R-mid) * arr[mid] + sum(arr[mid+1…mid+1]) + sum(arr[mid+1…mid+2]) + sum(arr[mid+1…R])$$
$$=(R-mid) * arr[mid] + \sum\limits_{l=mid+1}^R sum(arr[l…R])$$
发现：$\sum\limits_{l=mid+1}^R sum(arr[l…R])$ 是可以用线段树来维护的。
所以最后，我们维护几个值：
- 一个区间的 $sum$
- 一个区间的 $lsum$：指 $\sum\limits_{r=L}^R sum(arr[L…r])$
- 一个区间的 $rsum$：指 $\sum\limits_{l=R}^L sum(arr[l…R])$
- 一个区间的 $allsum$：指所求，即 $\sum\limits_{i=L}^{mid}\sum\limits_{j=mid+1}^R sum(arr[i…j])$
转移方程见代码。
• 注意到在线段树 $query$ 的过程中，合并的时候仍然要用转移方程，而不能直接用左右的 $allsum$ 的和。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
ll gcd(ll a, ll b) {
if (!b) return a;
return gcd(b, a%b);
}
ll cnt[maxn];
ll n,m; char op;
struct node {
ll lsum, rsum, sum, allsum;
ll lazy = 0;
} tr[maxn<<2];
ll C(ll a) {
return a * (a+1) / 2LL;
}
void push_down(ll cur, ll L, ll R) {
if (!tr[cur].lazy) return;
ll lazy = tr[cur].lazy;
tr[cur].lazy = 0;
ll mid = (L+R) >> 1;
ll l = cur<<1, r = l+1;
tr[l].lazy += lazy, tr[r].lazy += lazy;
ll llen = (mid - L + 1), rlen = (R - mid);
tr[l].sum += llen * lazy;
tr[r].sum += rlen * lazy;
tr[l].lsum += C(llen) * lazy;
tr[r].lsum += C(rlen) * lazy;
tr[l].rsum += C(llen) * lazy;
tr[r].rsum += C(rlen) * lazy;
tr[l].allsum += cnt[llen] * lazy;
tr[r].allsum += cnt[rlen] * lazy;
}
void push_up(ll cur, ll L, ll R) {
ll l = cur<<1, r = l+1;
ll mid = (L+R) >> 1;
ll llen = (mid - L + 1), rlen = (R - mid);
tr[cur].sum = tr[l].sum + tr[r].sum;
tr[cur].lsum = tr[l].lsum + tr[r].lsum + rlen * tr[l].sum;
tr[cur].rsum = tr[l].rsum + tr[r].rsum + llen * tr[r].sum;
tr[cur].allsum = tr[l].rsum * rlen + tr[r].lsum * llen + tr[l].allsum + tr[r].allsum;
}
void update(ll cur, ll l, ll r, ll L, ll R, ll val) {
ll len = (r-l+1);
if (L <= l && R >= r) {
tr[cur].lazy += val;
tr[cur].sum += len * val;
tr[cur].lsum += C(len) * val;
tr[cur].rsum += C(len) * val;
tr[cur].allsum += cnt[len] * val;
return;
}
ll mid = (l+r) >> 1;
push_down(cur, l, r);
if (L <= mid) update(cur<<1, l, mid, L, R, val);
if (R > mid) update(cur<<1|1, mid+1, r, L, R, val);
push_up(cur, l, r);
}
node query(ll cur, ll l, ll r, ll L, ll R) {
if (L <= l && R >= r) {
return tr[cur];
}
push_down(cur, l, r);
ll mid = (l+r) >> 1;
node lnode {}, rnode {}, curnode {};
ll llen = max(mid - max(L, l) + 1, 0), rlen = max(min(R, r) - mid, 0);
if (L <= mid) lnode = query(cur<<1, l, mid, L, R);
if (R > mid) rnode = query(cur<<1|1, mid+1, r, L, R);
curnode.sum = lnode.sum + rnode.sum;
curnode.lsum = lnode.lsum + rnode.lsum + rlen * lnode.sum;
curnode.rsum = lnode.rsum + rnode.rsum + llen * rnode.sum;
curnode.allsum = lnode.allsum + rnode.allsum + lnode.rsum * rlen + rnode.lsum * llen;
push_up(cur, l, r);
return curnode;
}
void init() {
cnt[1] = 1;
cnt[2] = 4;
for (ll i = 3; i <= maxn-5; i++) {
ll mid = (1+i) >> 1;
ll j = mid, k = i-mid;
cnt[i] = cnt[j] + cnt[k] + C(j) * k + C(k) * j;
}
}
int main() {
fastio;
cin >> n >> m;
init();
n--;
while (m--) {
cin >> op;
if (op == 'C') {
ll l,r,v; cin >> l >> r >> v;
r--;
update(1, 1, n, l, r, v);
} else {
ll l,r; cin >> l >> r;
r--;
ll res = query(1, 1, n, l, r).allsum;
int flag = 1;
if (res < 0) flag = -1;
res = abs(res);
ll d = C(r-l+1);
ll g = gcd(res,d);
res /= g;
d /= g;
if (flag < 0) cout << "-";
cout << res << "/" << d << "\n";
}
}
}
例4 CF850F Rainbow Balls
题意
有一个袋子，袋子中有 $n$ 种颜色的球，第 $i$ 种颜色的球有 $a_i$ 个。
现在持续进行以下操作：
有顺序地随机取出两个球，把第二个球涂成第一个球的颜色，然后把两个球都放回袋子。
求操作次数的期望，使得所有球的颜色相同？
• 可以证明最终答案为 $\frac{P}{Q}$ 的形式，输出 $P \times Q^{-1}$ 在 $\mod (10^9+7)$ 下的值。
其中，$n \leq 2500, 1 \leq a_i \leq 10^5$。
题解
一个比较明显的想法是：先决定最终的颜色。
在决定好最终颜色（比如红色）后，其他颜色都可以看作同一种颜色（非红色）。
在问题变成 红色/非红色 之后，可以发现使用 DP 可以表示递推状态。
并且 DP 的状态仅与 红色球 的数量有关。
令 $s = \sum\limits_{i=1}^na_i$ （表示总球数）。
令 $f_i$ 为：现在有 $i$ 个红色球，把所有球都变成 红色 的期望操作次数。
首先可以知道，$f_s = 0$，且 $f_0$ 不存在。
然后考虑转移方程：
对于 $f_i$ 来说，有 $i$ 个红色球，$(s-i)$ 个非红色球。
那么随机取两个球，能对状态产生影响的就两种情况：
- 红 + 非红 -> 红色球数 加 $1$
- 非红 + 红 -> 红色球数 减 $1$
这两种情况的样本大小均为 $i(s-i)$，而总样本空间的大小为 $s(s-1)$。
所以，令 $$p_i = \frac{i(s-i)}{s(s-1)}$$
则从 $f_i$ 转移到 $f_{i-1}, f_{i+1}$ 的概率均为 $p_i$，而什么都没发生（转移回 $f_i$）的概率为 $(1-2p_i)$。
如此，我们可以列出方程：
$$f_i = p_if_{i-1} + p_if_{i+1} + (1-2p_i)f_i + v$$
$v$ 是什么？
注意到转移时，也是会消耗 $1$ 次操作的。
• 但是注意，$v$ 不等于 $1$！
这是因为 $f_i$ 的意义是：最终颜色为红色 的情况下的操作期望值。
所以 $v$ 应该等于 这一次操作 被分到 最终颜色为红色 情况下的 贡献（对于期望值的贡献）。
相当于把 $1$ 次操作拆成很多份，每一份分别贡献给了每一种最终颜色对应的期望。
结论：$v = \frac{i}{s}$
证明：从字面上理解来看，$v$ 的值代表了在有 $i$ 个红色球的情况下，最终颜色为红色的概率。
所以我们求出这个概率即可。
设 $g_i$ 为：有 $i$ 个红色球的情况下，最终颜色为红色的概率。
易知 $g_0 = 0, g_s = 1$。
并且同上转移方程，可得方程：
$$g_i = p_ig_{i-1} + p_ig_{i+1} + (1-2p_i)g_i$$
即 $2g_i = g_{i-1} + g_{i+1}$，也就是 $g_{i+1} - g_i = g_i - g_{i-1}$，等差数列。
所以 $g_i = \frac{i}{s}$，证毕。
所以我们最终的方程就有了：
$$f_i = p_if_{i-1} + p_if_{i+1} + (1-2p_i)f_i + \frac{i}{s}$$
化简一下可得：
$$2f_i = f_{i-1} + f_{i+1} + \frac{s-1}{s-i}$$
其中，$f_s = 0, f_0$ 不存在。
处理不存在的值 $f_0$，我们不能把它当成 $\inf$，只能把其当成 $0$。
所以代入 $i=1$，有 $f_2 = 2f_1 - 1$。
$i$ 的有效值为 $i \in [1,s-1]$，未知量为 $f_1, f_2, …, f_{s-1}$，总共有 $(s-1)$ 个方程 和 $(s-1)$ 个未知量，发现是可以解出来的。
但是问题在于 $s$ 的范围高达 $2500 * 10^5$，不能直接用高斯消元来解。
所以只能手推式子了，联立 $(s-1)$ 个方程后，可以手推得出
$$f_1 = \frac{(s-1)^2}{s}$$
剩下的 $f_2, …, f_{s-1}$ 也可以得出了。
枚举所有最终颜色的情况，最终的答案就为 $ans = \sum\limits_i{f_{a_i}}$
代码
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
const int maxn = 2505;
const int maxm = 1e5+5;
ll qpow(ll a, ll b) {
ll res = 1;
while (b) {
if (b & 1) res = (res * a) % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
ll inv(ll a) {
return qpow(a, mod-2);
}
int n;
ll arr[maxn], s = 0;
ll f[maxm];
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> arr[i], s += arr[i];
f[1] = (s-1) * (s-1) % mod * inv(s) % mod; // f1 = (s-1)^2 / s
f[2] = (2 * f[1] % mod - 1 + mod) % mod; // f2 = 2f1 - 1
for (int i = 3; i <= maxm-5; i++) {
f[i] = (2 * f[i-1] % mod - f[i-2] - (s-1) * inv(s-(i-1)) % mod + 2LL * mod) % mod;
// f_k = 2f_{k-1} - f_{k-2} - (s-1)/(s-k+1)
}
ll ans = 0;
for (int i = 1; i <= n; i++) ans += f[arr[i]], ans %= mod;
cout << ans << endl;
}
例5 ABC224F
题意
给定一个字符串 $S$，仅包含 $1-9$ 的字符。
现在在任意两个字符之间添加 + 号，就可以得到一个算式。
求所有添加方案得到的算式的和。
其中，$|S| \in [1, 2 * 10^5]$。
题解
对于这种 “所有方案” 的题目，一般考虑下概率问题。
对于从右往左数的第 $i$ 位，我们考虑它作为个位数，十位数，百位数……的概率：
$i=1$：个位数概率 $p=1$
$i=2$：个位数概率 $p=\frac{1}{2}$，十位数概率 $p=\frac{1}{2}$
$i=3$：个位数概率 $p=\frac{1}{2}$，十位数概率 $p=\frac{1}{4}$，百位数概率 $p=\frac{1}{4}$
$i=4$：个位数概率 $p=\frac{1}{2}$，十位数概率 $p=\frac{1}{4}$，百位数概率 $p=\frac{1}{8}$，千位数概率 $p=\frac{1}{8}$。
可以得出结论：除了最高位等同于次高位的概率外，对于 $i=k$ 的情况，从个位数开始往上的概率分别为 $[\frac{1}{2}, \frac{1}{4}, \frac{1}{8}…]$
代码
#include <bits/stdc++.h>
using namespace std;
template<class T>
T qpow(T a, int b) {
T res = 1;
while (b) {
if (b & 1) res *= a;
a *= a;
b >>= 1;
}
return res;
}
int norm(int x) {
if (x < 0) {
x += mod;
}
if (x >= mod) {
x -= mod;
}
return x;
}
struct Z {
int x;
Z(int x = 0) : x(norm(x)) {}
int val() const {
return x;
}
Z operator-() const {
return Z(norm(mod - x));
}
Z inv() const {
assert(x != 0);
return qpow(*this, mod - 2);
}
Z &operator*=(const Z &rhs) {
x = (ll)(x) * rhs.x % mod;
return *this;
}
Z &operator+=(const Z &rhs) {
x = norm(x + rhs.x);
return *this;
}
Z &operator-=(const Z &rhs) {
x = norm(x - rhs.x);
return *this;
}
Z &operator/=(const Z &rhs) {
return *this *= rhs.inv();
}
friend Z operator*(const Z &lhs, const Z &rhs) {
Z res = lhs;
res *= rhs;
return res;
}
friend Z operator+(const Z &lhs, const Z &rhs) {
Z res = lhs;
res += rhs;
return res;
}
friend Z operator-(const Z &lhs, const Z &rhs) {
Z res = lhs;
res -= rhs;
return res;
}
friend Z operator/(const Z &lhs, const Z &rhs) {
Z res = lhs;
res /= rhs;
return res;
}
};
Z ans = 0;
int main() {
fastio;
string s; cin >> s;
int n = s.size();
Z e = 1, p = 1, num = 1;
for (int i = n-1; i >= 0; i--) {
Z c = s[i] - '0';
ans = ans + c * e;
e -= num * p;
p /= 2;
e += p * num * 11;
num *= 10;
}
cout << (ans * (qpow(Z(2), n-1))).val() << "\n";
}