区间缩小
题目描述
给定一个正整数 $n$,我们初始设定两个变量 $l$ 和 $r$,其中 $l=1$,$r=n$。我们将执行以下步骤:
- 如果 $l=r$,则结束操作;否则,执行步骤 $2$。
- 从区间 $[l,r]$ 中等概率地选取一个正整数 $x$。然后,以下两种情况互斥地发生:以概率 $p$ 将 $l$ 更新为 $x$,以概率 $1−p$ 将 $r$ 更新为 $x$。接着返回步骤 $1$。
经过上述操作,最终必然会有 $l=r$。设随机变量 $X$ 为最终得到的数字(即 $l$),求 $X$ 的数学期望。 答案对 $998244353$ 取模。
输入描述:
第一行给出两个正整数 $n,x$ $(1 \leq n \leq 10^6 ,0 \leq x \leq 100)$,其中 $n$ 的具体意义如题意所示。令 $p= \frac{100}{x}$ 。其中 $p$ 的意义如题意所示。
输出描述:
输出一个整数,表示答案。
示例1
输入
234 10
输出
898419942
解题思路
期望题就没一道会做的。
最关键的性质,看不出来就别想做出来了。定义 $E(l,r)$ 表示在区间 $[l,r]$ 内最终得到的数字的期望值,有 $E(l+x,r+x) = E(l,r) + x$。
简单证明。定义 $p_i \, (l \leq i \leq r)$ 表示最终得到的数字为 $i$ 的概率,那么有 $E(l,r) = \sum\limits_{i=l}^{r}{i \cdot p_i}$。而 $E(l+x,r+x) = \sum\limits_{i=l}^{r}{(i+x) \cdot p_{i+x}} = \sum\limits_{i=l}^{r}{i \cdot p_{i+x}} + x \sum\limits_{i=l}^{r}{p_{i+x}} = \sum\limits_{i=l}^{r}{i \cdot p_{i+x}} + x$。又因为区间 $[l,r]$ 与 $[l+x,r+x]$ 的长度一样,依据题意长度相同的区间最终得到数字的相对位置的概率相同,即 $p_i = p_{i+x}$,因此有 $E(l+x,r+x) = E(l,r)+x$。
所以对于每种长度的区间,我们只需求出 $E(1,i) \, (1 \leq i \leq n)$ 即可。用 dp 的思路求解该状态,即根据下一步左端点或右端点停留在哪个位置进行状态转移,有状态转移方程
$$
\begin{align*}
&E(1,i) = \sum\limits_{j=1}^{i}{\frac{p \cdot E(j,i)}{i}} + \sum\limits_{j=1}^{i}{\frac{(1-p) \cdot E(1,j)}{i}} \\
\Rightarrow \frac{i-1}{i} \cdot &E(1,i) = \sum\limits_{j=2}^{i}{\frac{p \cdot E(j,i)}{i}} + \sum\limits_{j=1}^{i-1}{\frac{(1-p) \cdot E(1,j)}{i}} \\
&E(1,i) = \frac{1}{i-1} \left({\sum\limits_{j=2}^{i}{p \cdot E(j,i)} + \sum\limits_{j=1}^{i-1}{(1-p) \cdot E(1,j)}}\right) \\
&E(1,i) = \frac{1}{i-1} \left({\sum\limits_{j=1}^{i-1}{p \cdot (E(1,i-j)+j)} + \sum\limits_{j=1}^{i-1}{(1-p) \cdot E(1,j)}}\right) \\
&E(1,i) = \frac{1}{i-1} \left(p \cdot \frac{(i-1) \cdot i}{2} + {\sum\limits_{j=1}^{i-1}{E(1,j)}}\right) \\
\end{align*}
$$
只需累加前缀 $E(1,1) + \cdots + E(1,i-1)$ 就可以实现 $O(1)$ 转移(需要预处理逆元)。
AC 代码如下,时间复杂度为 $O(n \log{\text{mod}})$:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 5, mod = 998244353;
int f[N];
int qmi(int a, int k) {
int ret = 1;
while (k) {
if (k & 1) ret = 1ll * ret * a % mod;
a = 1ll * a * a % mod;
k >>= 1;
}
return ret;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
m = 1ll * m * qmi(100, mod - 2) % mod;
f[1] = 1;
for (int i = 2, s = 1; i <= n; i++) {
f[i] = (s + i * (i - 1ll) % mod * qmi(2, mod - 2) % mod * m) % mod * qmi(i - 1, mod - 2) % mod;
s = (s + f[i]) % mod;
}
cout << f[n];
return 0;
}
参考资料
集美大学第十一届校程序设计竞赛 验题人题解:https://zhuanlan.zhihu.com/p/1431495113
标签:frac,limits,leq,cdot,sum,int,缩小,区间 From: https://www.cnblogs.com/onlyblues/p/18488078