Q779’s Blog

概率不等式 算法竞赛中有时会用到随机化算法，这些算法的正确性与时空复杂度通常依赖于「某些随机事件发生的概率很小」这一前提。 例如，快速排序的复杂度依赖于「所选的 pivot 元素几乎是最小或最大元素」这一事件较少发生。 本文将简要介绍一些用于分析随机化算法的工具并给出几个简单应用的例子。 Union bound 记 \(A_1,\cdots,A_m\) 为随机事件，则 \[ \mathrm{Pr}\left(\bigcup_{i=1}^m A_i\right) \leq \sum_{i=1}^m \mathrm{Pr}(A_i) \] 即：一组事件中至少一个发生的概率，不超过每一个的发生概率之和。 实际上，这一结论还可以稍作加强： 一组事件中至少一者发生的概率，不小于 每一个的发生概率之和，减掉每两个同时发生的概率之和。 一组事件中至少一者发生的概率，不超过 每一个的发生概率之和，减掉每两个同时发生的概率之和，加上每三个同时发生的概率之和。 …… 随着层数越来越多，交替出现的上界和下界也越来越紧。这一系列结论形式上类似容斥原理，证明过程也和容斥类似，这里略去。 Marko...

Markdown 缩进和换行 Markdown 一般不支持使用 Tab 和空格缩进，但是一般支持 HTML 转义字符。 &emsp; ：em space（全角空格） &ensp; ：en space（半角空格） &nbsp; ：Non-breaking space（不换行空格） 他们的换算关系是 1个  = 2个  = 4个  然后 Markdown 也不支持 Enter 换行（空行），一般用 HTML 的 <br> 来实现。

洛谷P5497 [LnOI2019SP] 龟速单项式变换(SMT) 题解 题目链接：P5497 [LnOI2019SP] 龟速单项式变换(SMT) 题意： 若正整数序列 \(a\) 中存在连续若干个正整数的和为 \(m\) 的倍数，则这个正整数序列 \(a\) 被称为“\(m\) 序列”。 给定 \(n\) 和 \(m\)，你需要知道长度为 \(n\) 的任意正整数序列 \(a\) 是否都是“\(m\) 序列”。 输入格式： 两个数，\(n\) 和 \(m\)。 输出格式： 如果成立输出 YES 否则输出 NO。 数据范围： \(1 \le n, m \le {10}^{18}\)。 显然 \(n < m\) 时构造 \([1,1,\cdots,1]\) 即可。 当 \(n \ge m\) 时，记 \(S_i = \sum_{1 \le j \le i}a_j\) ，则至少存在一对 \((l,r)\) 满足 \(S_l\equiv S_r\pmod{m}\) 又因为他们的差一定不为 \(0\) ，则区间 \([l+1,r]\) 的和是 \(m\) 的倍数，即 \(n \...

【数学】trick 3 奇偶与对称 核心知识： 表达式 \(f(a+x) = \pm f(b - x)\) 中 \(x\) 的符号“一正一负” 若 \(f(a+x) = f(b - x)\) ，则函数 \(f(x)\) 的图像关于直线 \(x = \frac{a+b}{2}\)​​ 对称。 特别地： 若 \(f(x)\) 的图像关于直线 \(x=a\) 对称，则 \(f(a + x)=f(a - x)\) 或 \(f(x) = f(2a - x)\) 若 \(f(x)\) 的图像关于 \(y\) 轴对称，则 \(f(x) = f(-x)\) ，此时 \(f(x)\) 为偶函数。 若 \(f(x) = 2b - f(2a - x)\) ，则函数 \(f(x)\) 的图像关于点 \((a,b)\)​ 对称。 特别地： 若 \(f(x)\) 的图像关于 \((a,0)\) 对称，则 \(f(x) = -f(2a - x)\) 。 若 \(f(x)\) 的图像关于 \((0,0)\) 对称，则 \(f(x) = -f(-x)\) ，此时 \(f(x)\)​ 为奇函数。 思想方...

【数学】tricks 2 以值代参 与二次函数零点有关的一类问题，比如：   “设 \(f(x) = x^2 + ax + b\) 在区间 \(D\) 上有两个零点，求 \(3a+b\)​ 的取值范围” 可以根据条件“区间 \(D\) 上有两个零点”构造一个关于 \(a,b\) 的不等式组，即构造一个可行域 再将 \(3a + b\)​ 看作目标函数，用线性规划来求解。这是一个费时费力的通法。 不过，如果我们换一个角度，将 \(3a + b\) 与函数值 \(f(3) = 9 + 3a + b\) 建立联系 用函数值来代替参数式，称之为“以值代参”，再根据韦达定理，用函数零点 \(x_1,x_2\) 来表示参数 \(a,b\) 。 题：已知函数 \(f(x) = x^2 + ax + b(a, b \in \mathbb{R})\) 在区间 \((0,1)\) 内有两个零点，求 \(3a + b\) 的取值范围。 解：记 \[ f(x) = x^2 + ax+ b = (x - x_1)(x - x_2)~(x_1,x_2 \in (0, 1)) \] 由韦达定理得 \[ \b...

【数学】tricks 1 奇穿偶回 非常简单形象，把多项式函数 \(f(x)\) 拆成形如 \[ f(x)= (x-x_0)^a(x-x_1)^b\cdots \] 那么零点 \(x_0\) 两侧的符号是否相等，取决于 \(x_0\) 上面的指数是否为偶数。 对于 \(f(x)\) 再乘上一个「不含 \((x-x_i)\) 的初等函数 \(g(x)\) 」的函数 如果 \(x_0\) 也是 \(g(x)\) 的零点，那 \(x_0\) 的指数相当于 \(1\)​ 。 特别地，\(g(x)\) 可以是绝对值函数，比如 \(|x-x_0|\) ，不过要将其视作 \((x-x_0)^2\) 。 定义 已知 \(x_0\) 是连续函数 \(f(x)\) 的零点，存在实数 \(\delta > 0\) ，设区间 \(I=(x_0-\delta,x_0 + \delta)\) 若对于任意 \(x \in I\) ，函数 \(f(x)\) 在区间 \(I\) 上的函数值均同号（图像位于 \(x\) 轴同侧）， 则称函数 \(f(x)\) 的图像在零点 \(x_0\) 处呈现“回”的现...

《具体数学》 2.6 有限微积分和无限微积分 注意，本文英文标题是 FINITE AND INFINITE CALCULUS ，不是定积分和不定积分。 本章实际上定义了不定和式 \(\sum g(x)\delta x\) 和和式 \(\sum_a^bg(x)\delta x\)​ 。 一、微分算子与差分算子 按照书本中的定义，无限微积分基于由 \[ \mathrm{D}f(x)=\lim_{h \to 0}\frac{f(x+h)-f(x)}{h} \] 所定义的微分（derivative）算子 \(\mathrm{D}\) 的性质。有限微积分则是基于由 \[ \Delta f(x) = f(x + 1) - f(x) \] 所定义的差分（difference）算子 \(\Delta\) 的性质。 差分算子是微分的有限模拟，其中限制了取 \(h\) 的正整数值。 于是当 \(h \to 0\) 时，\(h=1\) 是我们所能达到的最近的“极限”，则 \(\left.\Delta f(x)=\frac{f(x+h)-f(x)}{h}\right|_{h=1}\) 符号 \(\ma...

洛谷P6046 纯粹容器 题解 题目链接：P6046 纯粹容器 题意： 白王制造了 \(n\) 个容器，并将它们排成了一队，从左到右依次编号为 \(1 \sim n\)。第 \(i\) 个容器的强度为 \(a_i\)，保证 \(a_i\) 互不相同。为了挑选出最纯粹的容器，白王会进行 \(n-1\) 轮操作，每轮操作中，他会等概率随机挑选两个 位置相邻 且 未被击倒 的容器，令它们进行决斗，在一次决斗中，强度较小的容器将会被击倒并移出队列。 显然最后留下的是强度最大的容器，但是，可怜的容器们很想知道自己能够活多久，于是，它们请你对每个容器求出它存活轮数的期望。答案对 \(998244353\) 取模。 一个容器的存活轮数为最大的非负整数 \(x < n\) 满足它在第 \(x\) 轮未被击倒。 两个容器 \(i\) 和 \(j\) 位置相邻当且仅当不存在 \(k\) 满足 \(i<k<j\) 且 \(k\) 号容器未被击倒。 输入格式： 第一行一个整数 \(n\)。 第二行 \(n\) 个整数 \(a_1, a_2,\cdots,a_n\)，意义见题目描述。 ...

Linux 压缩包中文乱码 解决方案 好久没写 Linux 相关的文章了，主要是我的 Ubuntu 现在不用了。 这篇文章可以算是欠了很久的文章，一直没写，今天理东西的时候发现的。 解决方案： 万能的终端指令： unzip -O CP936 xxx.zip CP936其实就是GBK，IBM在发明Code Page的时候将GBK放在第936页，因此叫CP936

CF1969C Minimizing the Sum 题解 题目链接：Minimizing the Sum 题意： 给你一个长度为 \(n(1 \le n \le 3 \times 10^5)\) 的整数数组 \(a(1 \le a_i \le 10^9)\)。 你可以执行以下操作：选择数组中的一个元素，并用其邻近元素的值替换它。 你的任务是计算在执行上述操作最多 \(k(0 \le k \le 10)\) 次的情况下，数组的总和可能达到的最小值。 注意到 \(k\) 十分的小，我们可以直接dp 设 \(f_{i,j}\) 表示前 \(i\) 个数修改 \(j\) 次的最小值。转移就钦定 \([l+1,~i]\)​ 全部推成最小值。 时间复杂度 \(\mathcal{O}(nk^2)\) 代码：（考场上光速写的，可能不够优雅） #include <bits/stdc++.h> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f void up(int &x,int y...

洛谷P5104 红包发红包 题解 题目链接：P5104 红包发红包 题意： 这个抢红包系统是这样的：假如现在有 \(w\) 元，那么你抢红包能抢到的钱就是 \([0,w]\) 等概率均匀随机出的一个实数 \(x\)。 现在红包发了一个 \(w\) 元的红包，有 \(n\) 个人来抢。那么请问第 \(k\) 个人期望抢到多少钱？ 输出答案对 \(10^9+7\) 取模后的结果。 输入格式： 一行三个整数，\(w,n,k\)。 输出格式： 第 \(k\) 个人期望抢到的钱数对 \(10^9+7\) 取模后的结果。 补充：期望可能是分数，关于分数取模，可以问度娘。 数据范围： 注意红包发明的抢红包系统和微信的抢红包系统不一样，红包发明的抢红包系统中的钱不一定是整数分。 对于 \(30\%\) 的数据，\(k=1\) 另有 \(30\%\) 的数据，期望值取模前为整数，\(k\le 10\)。 对于全部数据，\(0< w< (10^9+7)\)，\(n\le 10^{18},k\le n\)。 注意这道题随机出来的是实数，因此这道题是的随机变量 \(X\) 是连续性随...

条件期望与全期望公式 条件期望的定义 条件期望根据随机变量的不同有较多定义。 设 \(X\) 和 \(Y\) 都是离散型随机变量，则 \(X\) 在给定事件 \(Y=y\) 条件时的条件期望 \[ \begin{aligned} \mathrm{E}(X \mid Y=y) & =\sum_x x\cdot \mathrm{Pr}(X=x \mid Y=y) \\ & =\sum_x x \cdot\frac{\mathrm{Pr}(X=x, Y=y)}{\mathrm{Pr}(Y=y)} \end{aligned} \] 设 \(X\) 是连续性随机变量， \(Y\) 是离散型随机变量，则 \[ \mathrm{E}(X \mid Y=y)=\int_{-\infty}^{\infty} x f_X(x \mid Y=y) \mathrm{d} x \] 设 \(X\) 和 \(Y\) 都是连续型随机变量，联合密度函数为 \(f_{X, Y}(x, y)\) ，\(Y\) 的密度函数为 \(f_Y(y)\) ，\(X\) 的条件概率密度函数 \(f_{X\mi...