Q779’s Blog

洛谷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...

【专栏】概率与期望 之前写过很多概率与期望的内容，但是缺乏有效的整理 因此这篇文章主要起到查询对应内容的作用，并不会摘录全部内容。 下文统一使用 \(\mathrm{E}(X)\) 表示期望，\(\mathrm{Pr}(X)\)​​​ 表示概率。（尽管各文章的表示方式可能不同） 一、概率 相关文章：全概率公式&贝叶斯公式 设随机事件的样本空间为 \(\Omega\) ，\(\Omega\) 的一个子集称为事件。对于 \(\Omega\) 中的每一个事件 \(A\) 都有实函数 \(\mathrm{Pr}(A)\)​ 满足 非负性：\(\mathrm{Pr}(A) \ge 0\) 规范性：\(\mathrm{Pr}(\Omega)=1\) 可数可加性：对可数个两两互斥事件 \(\left\{A_i\right\}_{i \in N}\) 有 \[ \sum_{i=1}^{\infty} \mathrm{Pr}\left(A_i\right)=\mathrm{Pr}\left(\bigcup_{i=1}^{\infty} A_i\right) \] 任意一个满足上述条件...

CF1042E Vasya and Magic Matrix 题解 题目链接：Vasya and Magic Matrix 题意： 瓦西亚得到了一个大小为 \(n \times m\) 的魔法矩阵 \(a\)。矩阵的行从上到下编号为 \(1\) 到 \(n\)，列从左到右编号为 \(1\) 到 \(m\)。设 \(a_{ij}\) 是第 \(i\) 行和第 \(j\) 列的交点处的元素。 瓦西亚还得到了一个芯片。最初，芯片位于第 \(r\) 行和第 \(c\) 列的交点处（即元素 \(a_{rc}\) 处）。瓦西亚执行以下过程，只要可能：在所有矩阵元素中，其值小于芯片所在元素的值，瓦西亚随机且等概率地选择一个元素，并将芯片移动到该元素。 移动芯片后，他将其得分增加到这些元素之间的欧几里德距离的平方（即芯片现在所在的元素与芯片移动前所在的元素之间的距离）。当没有元素的值小于芯片所在元素的值时，过程结束。 矩阵元素之间的欧几里德距离，其坐标分别为 \((i_1, j_1)\) 和 \((i_2, j_2)\)，等于 \(\sqrt{(i_1-i_2)^2 + (j_1-j_2)^2...

OI思维水平的练习与提升 声明：以下观点大部分为本人的自我总结，可能不适用于所有人。 本文主要谈论的是思维水平，代码水平在本人看来就是熟能生巧的问题。 1. 怎么知道自己的思维水平？ 关于标题，答案其实很简单，你能想出什么难度的题你就有什么思维水平。 首先题目的思维难度可以这么理解 有的题目仅要求你推导出一个函数。 有的题目要求你推出函数的同时，找到函数在特定区间内的特殊性质。 有的题目不仅要求你推出函数、找到特殊性质，还需要合理利用特殊性质（比如选用合适的算法优化）。 其实就是思维深度和广度问题。 如果你只能想出第二种题，那你的思维水平就是第二级。以此类推。 然而有些时候你发现，你要想很久很久才能想出第二种题，或者和正解有那么一丢丢差距 那么其实可以认为，你实际上具备了这种层次的思维水平，但不具备应有的熟练程度。 2. 什么是熟练程度？ 下图（详见参考文献[1]）是 Um_nik 巨佬在 blog 里给出的 实际上我定义的思维水平是离散的，也就是图中的红点。 而思维的熟练度描述了我们的水平是如何随时间连续增长的（毕竟思维能力可不会轻易的大幅增加）。 也可以这么理解我的...

《具体数学》 2.4 多重和式 一、基本法则 本章节其实非常简单，特别是对于 OIer 来说。 下面就是一个简单的多重和式 \[ \sum_{i=1}^n\sum_{j=1}^mF(i,j) \] 对于多重和式，有一个被称为交换求和次序的基本法则，它推广了我们在 2.3 中定义的结合律。 \[ \sum_{P(i,j)}a_{i,j} = \sum_{i}\sum_{j}a_{i,j}[P(i,j)] = \sum_{j}\sum_{i}a_{i,j}[P(i,j)] \] 如何理解呢？其实就是下面的代码 for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(P(i,j)) ans += a[i][j]; for(int j = 1; j <= n; j++) for(int i = 1; i <= n; i++) if(P(i,j)) ans += a[i][j]; 于是可以进一步推导出和式的一般分配律 \[ \sum_{i\in A,~j \in B}a_ib_j = \...

SP1026 FAVDICE - Favorite Dice 题解 题目链接：FAVDICE - Favorite Dice 题意： 多组询问。 一个 \(n(1\le n \le 1000)\) 面的骰子，求期望掷几次能使得每一面都被掷到。 前置知识：一件事有 \(\frac{1}{p}\) 的概率完成，则期望要做 \(p\) 次。 那么这题就很简单了。设 \(f_i\) 表示扔出 \(i\) 个点数的期望步数，则 \[ f_i = f_{i-1} + \frac{n}{n-(i-1)} \] 后面那个就是 \(i-1\) 个点数的时候有 \(\frac{n-(i-1)}{n}\) 的概率扔出其他的点数，所以期望就是倒数。 时间复杂度 \(\mathcal{O}(n)\) 代码： #include <bits/stdc++.h> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f void up(int &x,int y) { x < y ? x =...

CF1965A Everything Nim 题解 题目链接：Everything Nim 题意： Alice 和 Bob 又在玩他们该死的游戏。 有 \(n(1\le n \le 2\times 10^5)\) 堆石子，记石子数最小的那一堆有 \(k\) 个石子 则一轮游戏（一局游戏有若干轮）中，可以选择同时从每个堆中取走 \(x(1\le x \le k)\) 个石子。 如果到谁取的时候，没有任何石子存留了，则他就输了。 假设两个人都十分聪明，则当 Alice 先手时是否必胜？ 如果最小的堆数为 \(1\) ，则 Alice 和 Bob 会一直取，直到出现一个堆不为 \(1\) 。 显然他们会取 \(\operatorname{mex}(a_i) - 1\) 次，因此 \(\mathrm{mex}\) 的奇偶性决定了事实上他们谁是先手。 可以证明，当 \(\mathrm{mex}(a_i) < \max(a_i)\) 时，先手必胜，否则取决于 \(\mathrm{mex}\) 的奇偶性。 因为先手取 \(k-1\) 个可以一直维持自己的先手状态，而在最后剩下的一堆取...

CF1966B Rectangle Filling 题解 题目链接：Rectangle Filling 题意： 给定一个 \(n\times m(1 \le n, m \le 500)\) 的方格矩阵，每个格子是黑色或白色的。 你可以执行若干次以下操作： 选择两个颜色相同的位置 \((x_1,y_1),(x_2,y_2)\) 将由这两个点构成的矩形区域染成 \((x_1,y_1)\) 对应的颜色。 \(1 \le t \le 10^4,\sum nm \le 3\times 10^5\)​ 。 显然，如果矩阵的四角中，存在对角颜色相同，则一定有解。 于是只剩下了这四种情况 比如对于第一种情况，我们只需要第一行有个黑的格子（四角除外），或者第 \(n\) 行有个白的格子，就有解了 时间复杂度 \(\mathcal{O}(\sum nm)\) 代码： #include <bits/stdc++.h> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f typedef p...

CF1966A Card Exchange 题解 题目链接：Card Exchange 题意： 你有 \(n\) 张卡片，每张卡片写着一个数 \(a_i\) 。 给定一个正整数 \(k\) ，定义一次操作为，选 \(k\) 张数字相同的卡片， 然后把他们替换成 \(k-1\) 张任意数字的卡片，这 \(k-1\) 张上写的可以互不相同。 问最少可以持有多少张卡片。（下图是 \(k=3\) 的例子） 输入格式： \(t (1\le t \le 500)\) 组数据 每组给出第一行 \(n,k(1 \le n \le 100,2\le k \le 100)\) ，第二行给出 \(a_i(1\le a_i \le 100)\)​ 。 输出格式： 对于每组数据，输出答案。 容易发现，只要有一种卡牌的数量超过 \(k\) ，答案就是 \(k-1\) ，否则一定是 \(n\) 。 因为我们可以把超过 \(k\) 张的那种卡片转换成相同的其他数字的卡片，进而消灭那种数字的多余牌数。 时间复杂度 \(\mathcal{O}(tn)\) ，空间复杂度 \(\mathcal{O}(V=\max...

CF1399E2 Weights Division (hard version) 题解 题目链接：CF1399E2 Weights Division (hard version) 题意： 给出一个结点数量为 \(n\) 的边带权的有根树，树的根结点为 \(1\)。你可以进行以下操作。 选定任意一条权值为 \(w_i\) 的边，使 \(w_i \gets \lfloor \frac{w_i}{2} \rfloor\)，花费为 \(c_i\) 且 \(c_i \in \{1, 2\}\)。 定义 \(w(i,j)\) 为结点 \(i\) 到结点 \(j\) 的路径边权和。 对于每组测试数据，你需要回答最小的花费，使得 \(\sum\limits_{v\in \mathtt{leaves}}w(\mathtt{root},v)\leq S\) 其中 \(\mathtt{leaves}\) 为叶子结点编号的集合。 输入格式： 输入的第一行包含一个整数 \(t\) (\(1 \le t \le 2 \cdot 10^4\)) — 测试用例的数量。接下来是 \(t\) 个测试用例。 每...

CF1338C Perfect Triples 题解 题目链接：Perfect Triples 题意： 通过如下方式构造一个无穷数列 \(S\)： 1. 选择一个字典序最小的有序三元组 \((a,b,c)\) ，且满足 \(a,b,c \notin S~, a \oplus b\oplus c=0\)。 2. 将 \(a,b,c\) 依次加入数列 \(S\)。 \(T(T \le 10^5)\) 组询问，每次给出一个数 \(n(1\le n\le 10^{16})\) ，求数列 \(S\) 的第 \(n\) 项。 打表找规律题，打表程序： #include <bits/stdc++.h> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f void up(int &x,int y) { x < y ? x = y : 0; } void down(int &x,int y) { x > y ? x = y : 0; ...