首页 > 其他分享 >区间缩小

区间缩小

时间:2024-10-20 22:31:36浏览次数:2  
标签:frac limits leq cdot sum int 缩小 区间

区间缩小

题目描述

给定一个正整数 $n$,我们初始设定两个变量 $l$ 和 $r$,其中 $l=1$,$r=n$。我们将执行以下步骤:

  1. 如果 $l=r$,则结束操作;否则,执行步骤 $2$。
  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

相关文章

  • P1880 [NOI1995] 石子合并 区间DP 记忆化DFS模拟DP
    P1880[NOI1995]石子合并诈骗题,看着像贪心,实际上是DP对贪心的hack:6346542如果使用贪心法求最小得分,应该是如下的合并步骤:第一次合并3465422,3合并得分是5第二次合并546545,4合并得分是9第三次合并96545,4合并得分是9......
  • [区间dp]合并石子升级版
    题目描述还记得经典题石子合并吗?现在小YYY将题目加强啦!在一个圆形操场的四周摆放着nn......
  • 区间与或
    前言抽象模拟赛,我现在菜的可怕题面疑似自出题,反正不难,就不找原题了挂个pdf题目下载算法显然可以用线段树维护观察到与运算和或运算的优先级不好处理,考虑每一位分开处理(位运算常见处理方法)如果是与运算,一旦为\(0\),就只需要把前面的或与运算的\(\rm{lazy_......
  • 双指针维护可交换结合贡献区间价值的正攻法
    对于一类区间价值V(l,r)=a[l]opta[l+1]opt...opta[r]当我们维护双指针同时需要维护内部区间的价值时,如果操作可交换结合并且可消去(存在y,xopty=0),l右移时直接去掉a[l]的价值即可;如果不可消去但可重复贡献(xoptx=x),可以使用ST表计算区间贡献;如果只满足结合律,我......
  • 区间dp板子
    比较简单的dp,但是建模可能会比较困难。以P1775石子合并(弱化版)为例(https://www.luogu.com.cn/problem/P1775)思路:要求1-n的石子合并的代价,可以看成小的区间问题,化为1-k+k-n的两个区间。然后就有递推式子:dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+w[j]-w[i-1]。编......
  • ABC292G Count Strictly Increasing Sequences [区间DP]
    Description你有\(n\)个数,每个数长度为\(m\)。不过这\(n\)个数中,可能有某些位不确定,需要你在每个?位置上\(0\)到\(9\)之间填一个数。设你填出来的序列是\(\{S_i\}\)。请你求出,在所有可能的填数方案中,有多少种满足\(S_1<S_2<\dots<S_n\)?对\(998244353\)取......
  • 获取字符串的在html页面上的宽度并且若文字过长则缩小字体填充
    某个页面有这样一个需求:一个固定宽度的div,若文字过长,则缩小字体填充。看到同事采用的是用php的GD库的imagettfbbox函数来计算文字的宽度。imagettfbbox(float $size,float $angle,string $font_filename,string $string,array $options=[]): array|false 取得使用Tru......
  • 区间DP问题归纳总结
    常见问题:常用技巧:将环形区间转变为线形区间,从而解决环形区间的问题区间dp记录方案数区间dp和高精度的结合(将高精度模板结合到dp中去)代码的实现方式有两种:迭代式:自底向上递推计算,适用于简单的dp过程,一般来说,状态用了几维,就需要写几层for循环,当dp维度较高时显然不适用......
  • 合并、删除区间算法C++代码
    #include<algorithm>#include<iostream>#include<vector>usingnamespacestd;classSolution{public:constintCOMBINE_INT=0;//1表示整数点区间,比如[1:3]和[4:5]会合并为[1:5],0则仅会合并[1:3]和[3:4]这类的区间。vector<pair<int,int>>......
  • 八大排序--04希尔排序(缩小增量排序)
    假设数组arr[]={0,3,1,2,5,7,4,6},请通过插入排序的方式,实现从小到大排列:方法:将数组按照数组长度的一半为间隔进行分组,组内进行插入排序,小的数据在前面,大的数据在后面; 将数据按照数组长度一半的一半为间隔进行分组,组内进行插入排序;重复上述步骤,直到无法继续分组(步长为1时),整个......