区间缩小

onlyblues / 2024-10-30 / 原文

区间缩小

题目描述

给定一个正整数 $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;
}