Posts

同余最短路看名字感觉很难，但其实非常简单，也好理解，先说一道题： 题目 原型：洛谷P3403 跳楼机 有一栋 $h$ 层的大楼（层数编号从 $1$ 到 $h$），有 $n+1$ 种移动方式： 回到 $1$ 层 向上走 $x_1 \sim x_n$ 层 楼层不是循环的，你无论如何都无法到达 $h+1$ 层或以上。 最初你可以在任意一层（但也无关紧要），问你能到达多少个不同的楼层。 题解 分类 我们按楼层模 $x_1$ 的余数分类，把楼层 $i$ 分到 $i \bmod x_1$ 类。 这样分类有什么用呢？见下。 定义状态 有了这个分类，我们可以定义状态 $d_i$（$i \in [0,x_1)$）代表不用「向上走 $x_1$ 层」操作能到达的、最小的第 $i$ 类楼层是多少。 那么，由于有「向上走 $x_1$ 层」操作，所以 $d_i,d_i+x_1,d_i+2x_1,\dots$（比 $d_i$ 大或相等的第 $i$ 类楼层）都是可达的。 接下来考虑转移这个状态。 转移 其实也很好想，比如用一次「向上走 $x_2$ 层」操作，那么 $d_i$ 可以转移到 $d_{(i+x_2) \bmod x_1}$，转移代价为 $x_2$，所以： $d_{(i+x_2) \bmod x_1}=\min(d_{(i+x_2) \bmod x_1},d_i+x_2)$ ...

要说行列式，就得先说一下矩阵（其实是方阵）的秩的定义。 对于一个方阵，其秩的定义就是矩阵里线性无关的极大值。 听这个定义有点难懂，这里解释一下。 其实一个方阵就可以被当做是一个没有右项的方程集。 而一个方阵的秩就可以当做是，这个没有右项的方程集在经过高斯消元后，非 $0$ 行的数量。 有了这个定义，矩阵的秩还可以被当做是，这个没有右项的方程集中，不会被其他方程替代掉的方程数量： 解释一下，如果方程长这样： $ \begin{cases} -x_1+2x_2+5x_3=11 \ 2x_1=8 \ x_1+2x_2+5x_3=19 \end{cases} $ 那么，其实第三个方程式可以通过前两个方程式推出来，也就称作第三个方程式可以被前两个方程式替代掉。 知道了“替代”的定义后，就知道了一件事，就是上面说的“会被其他方程替代掉的方程”，这些方程可以直接从方程组里去掉，而不影响最终的解。 所以，我们就可以对奥数里的一个点做一个更简洁的解释： 在奥数里，讲了解 $n$ 元一次方程（组）的方法。 同时还说了，在这个 $n$ 元一次方程组内，如果“有用”的方程数量，刚好等于未知数的数量，或者大于未知数的数量，那么这个方程组就有唯一解。 这一点可以被更简洁地解释为： 这个 $n$ 元一次方程组，转化为“高斯矩阵”，并删除最后一列后（变成 $n \times n$ 的方阵），如果这个方阵的秩刚好为 $n$，那么这个方程组就有唯一解。 然后，我们回归正题，说行列式。 行列式是对于一个方阵来讲的，一个方阵有行列式有且仅当这个方程的秩刚好等于方阵的大小（行或者列）。 行列式的定义此处不讲，因为： 太复杂了 （几乎）没有用处 行列式的计算方法是用的高斯消元。 在高斯消元的思路里，提到了三种“基本行变换”：（以下全部以高斯矩阵的角度去说） 将一行全部乘上一个非 $0$ 实数 $x$，解不变。 将一行内的所有元素对应地加上/减去另一行对应的元素乘上一个非 $0$ 实数 $x$，解不变。 交换两行，解不变。 这三种基本行变换在执行前后，行列式并不是都不变的： 将一行全部乘上一个非 $0$ 实数 $x$，行列式也会乘上 $x$。 将一行内的所有元素对应地加上/减去另一行对应的元素乘上一个非 $0$ 实数 $x$，行列式不变。 交换两行，行列式变号（负数变成正数，反之亦然）。 所以我们只用写一下高斯消元，然后处理一下对行列式的值的变化即可。 但这儿还有一点问题，就是行列式怎么求。 求法很好记，如果说当前方阵是个上三角矩阵（设方阵叫 $a$，那么 $a$ 是个上三角矩阵有且仅当对于所有的 $(i,j)$，如果满足 $i>j$，那么 $a_{i,j}$ 一定要等于 $0$，当然其他方格不做要求），那么这个方阵的行列式就是这个方阵中正对角线上的元素的乘积。 ...

说一个非常重要的语法错误。 如果你写这样一句话： v[x] = newnode(); 其中： v为一个vector。 x为不越界的非负整数，且不会变化。 newnode()函数内会向vector内push_back一个新元素，并返回加入元素（即最后一个元素）的下标。 那么，你会发现，v[x]的值并不是这样变化的： 1,2,3,4,5,6,7,... 而是类似于这样的：（非真实输出结果，仅供参考） 1,1,2,2,3,4,4,5,6,7,8,8,9,10,11,12,13,14,15,16,16,17,18,19,20,... 你会发现部分情况下，v[x]没有变化！ 这实际上是因为vector的内部机制。 vector会有一个capacity，就是提供的内存大小。 每次push_back的时候，如果说加入后，不超过当前的capacity，就会直接加入。 否则，vector会新开辟一块等于当前capacity的两倍（这个在不同编辑器上是不一样的，有些可能是每次新增 $5$ 个）的新空间，并把原本的数据拷进这块新空间内。 比如说现在的vector是： 内存354~357位置：3 1 2 4 且capacity是 $4$，那么我们如果尝试push_back一个 $5$，则vector就会发现大于了capacity，便会新开一块等于当前capacity的两倍的空间： 内存354~357位置：3 1 2 4 内存382~389位置： 并把当前数据拷进去： 内存354~357位置：3 1 2 4 内存382~389位置：3 1 2 4 然后在新空间内加入 $5$： 内存354~357位置：3 1 2 4 内存382~389位置：3 1 2 4 5 并把所有v[x]指向的内存都改成382~389这块新内存内对应的地方。 不过由于C++的赋值机制，系统会先找到要赋值给的变量的指针，然后求出要赋的值，赋给以前找到的指针。（这一步是推测，可能不准确） 所以就会导致把newnode()的值赋给了原本的v[x]，导致输出的时候访问的新v[x]值出错。 解决方法也很简单，把newnode()用个临时变量t存储，并将v[x]赋值为t即可。

在数学、编程界里，可能会经常遇到方程，而且有时候还会遇到一种特殊方程——一元二次方程。 除此之外，还有含参一元二次方程，这里也会一起讲。（待补充） 其实还有如二元一次方程、一元三次方程等的特殊方程，但在这里不讲。 一元二次方程 有人看到“一元二次方程”就不知道是啥意思，这里先说一下定义 定义 首先，方程相信大家都见过，所以这里不写对方程的定义解释。（废话 而 $x$ 元 $y$ 次方程就是这么定义的： 这个方程经过化简后，共有 $x$ 个未知数，且未知数上的最大指数为 $y$ 的方程。 如： $3(x+1)=6x$：一元一次方程，也是最常见的方程。 $3(x+1)^2=2(x+1)$：一元一次方程，因为两边可以同时除以 $x+1$ 以让指数减少 $1$。 $x^2-4x+1=0$：一元二次方程，也是下面要讲的方程类型。 $x^3+2x^2-1=16x$：一元三次方程，也是一种不常见的方程类型。 讲完定义，接下来说怎么解 解法 推导 我们把方程一般化，变成： $ax^2+bx+c=0$ 其中 $a$、$b$、$c$ 均为常量。 然后，我们不断对方程做一些推导。 移项 $ax^2+bx=-c$ 同时除以 $a$ 常量 $x^2+\dfrac{b}{a}x=-\dfrac{c}{a}$ 这个式子很多人看了就不知道怎么继续推导了。 但还是可以继续转化的。 我们考虑配方，即把式子的左/右项同时加/减/乘/除一个相同的数，然后让这个等式的左/右项变成一个数的平方的形式。 这一步比较考验数感，一个结论就是，我们同时加上 $\left( \dfrac{b}{2a} \right)^2$ 常量 即可。 $x^2+\dfrac{b}{a}x+\left( \dfrac{b}{2a} \right)^2=-\dfrac{c}{a}+\left( \dfrac{b}{2a} \right)^2$ 化简 $\left( x+\dfrac{b}{2a} \right)^2=\dfrac{-c}{a}+\dfrac{b^2}{4a^2}$ 二次化简 $\left( x+\dfrac{b}{2a} \right)^2=\dfrac{b^2-4ac}{4a^2}$ 同时开根号 $x+\dfrac{b}{2a}=\sqrt{\dfrac{b^2-4ac}{4a^2}}$ ...

感谢这篇文章的作者 整除分块主要解决求解 $\sum\limits_{i=1}^n \lfloor \frac{n}{i} \rfloor$ 的值。 一看这个公式，可能毫无头绪，但画张图你就有点思路了：（$n=11$） （灰色线：$y=\frac{11}{x}$，绿色点：$y=\lfloor \frac{11}{x} \rfloor$，橙色线：仅为辅助） 这张图其实就是在提示我们： $\lfloor \frac{n}{i} \rfloor$ 的值随着 $i$ 的增长而非单调递减 $\lfloor \frac{n}{i} \rfloor$ 的值往往会在一段区间内相等 所以，我们就有一个思路了，就是求出所有值（下面的“值”都代指的是 $\lfloor \frac{n}{i} \rfloor$）相等的极大区间集，然后就可以快速统计了。 有人问，这不就是个常数级别的优化吗，怎么能叫“快速”呢？其实区间个数总是 $O(\sqrt{n})$ 级别，最多约 $2 \times \sqrt{n}$。 证明： 我们把 $i$ 分成两部分去考虑，一部分是 $i \leq \sqrt{n}$，另一部分是 $i>\sqrt{n}$。 在第一部分内，$i$ 也就只有 $\sqrt{n}$ 种取值，$\lfloor \frac{n}{i} \rfloor$ 最多只有约 $\sqrt{n}$ 种取值。 在第二部分内，$\lfloor \frac{n}{i} \rfloor$ 在 $i$ 最小时（$i=\sqrt{n}+1$）会达到最大值，约 $\sqrt{n}$；而上面说“$\lfloor \frac{n}{i} \rfloor$ 的值随着 $i$ 的增长而非单调递减”，所以易得 $\lfloor \frac{n}{i} \rfloor$ 最多也只有约 $\sqrt{n}$ 种取值。 $\lfloor \frac{n}{i} \rfloor$ 的总取值种数最多只有第一、二部分的取值个数和，即 $2 \times \sqrt{n}$，证毕。 ...

整体二分类似于线段树上二分，在讲这个算法前，先引入几个问题。 解决题型 整体二分一般解决的是如下的问题： 给你一个【集合/序列/矩阵/树】，要求【静态/动态】维护所有【元素/区间/子矩阵/链/子树】中的第 $k$【可能每次给定】大元素，【可能强制在线】。 下面是一堆例题。 例题1 动态查询集合第k大（可离线） 题意 让你维护一个初始为空的多重集合 $s$，并支持 $q$ 次操作，操作都是下面三种之一： 添加一个数 $x$ 到集合 $s$ 中。 在集合 $s$ 中删除一个数 $x$（保证元素存在）。 查询集合第 $k$ 大（保证第 $k$ 大存在）。 数据范围 $1 \leq q \leq 2 \times 10^5$ $0 \leq x \leq 10^9$ 题解 维护一个权值线段树（权值线段树其实就是一个维护值域的线段树），维护一段值域里有多少个数，每次询问在线段树上二分即可。 具体地，对于线段树上某个节点对应的区间 $[l,r]$，这个节点上的值为集合中，值在 $[l,r]$ 的数的个数有多少。 在询问时，我们要记录当前节点编号 $x$，$x$ 维护区间 $[l,r]$，以及要查询值在 $[l,r]$ 内的所有数的第 $k$ 大。 当递归到某个状态后，我们看这个节点的左子树 $\text{lc}$ 内有多少个值，如果大于等于 $k$，则递归到左子树；否则递归到右子树，且 $k$ 减去(左子树内数的个数)。 由于值域较大，权值线段树可能会爆，所以要先把所有询问离线下来，做个离散化，然后就可以把 $x$ 控制到 $q$ 级别，就不会爆了。 ...

中国剩余定理，Chinese Remainder Theorem，又称CRT，我们接下来就讲一下这个算法的原理。 要说原理，就得从古代说起。 （你到底是在讲编程课还是在讲历史课） （真的是在将编程课） 在古代，有一个问题，叫做“物不知数问题”，原文是这样的： 有物不知其数 三三数之剩二 五五数之剩三 七七数之剩二 问物几何？ 这个问题翻译过来就是问以下方程的所有正整数解： $ \begin{cases} x \equiv 2 \pmod{3} \ x \equiv 3 \pmod{5} \ x \equiv 2 \pmod{7} \end{cases} $ 这个问题在后来有一个解了，解出来这个问题的人，编了一首诗，叫做“孙子歌诀”，原文： 三人同行七十稀 五树梅花廿一支 七子团圆正半月 除百零五便得知 这个解翻译过来就是说，若设 $r_3$ 为方程中 $x$ 模 $3$ 的余数，$r_5$、$r_7$ 同理，那么所有解 $x$ 一定满足： $x \equiv r_3 \times 70+r_5 \times 21+r_7 \times 15 \pmod{105}$ 其中 $105$ 的实际来源是上面三个方程的模数的 $\text{lcm}$，即 $\text{lcm}(3,5,7)=3 \times 5 \times 7=105$。 关于 $70$、$21$、$15$ 的来源下面再说，我们先证明一下这个解是正确的。 由于 $105$ 是三个模数的 $\text{lcm}$，所以说如果 $x$ 是满足条件的，$x-105$、$x+105$ 都是满足条件的（此处暂时忽略“正整数解”的限制），显然。 ...

有人问，组合数学不是就一些简单的公式吗？不是的，其实组合数学是数学中的一个非常庞大的分支，接下来就举一些例子。（更新中） 本文主要讲各种数据范围下，求组合数的方式；以及球盒模型各种情况下的公式；最后是一些球盒模型的扩展情况。 转到：球盒模型公式 转到：球盒模型扩展公式 （下面部分标题里的LaTeX公式更新后炸了，就凑合着看吧） 求组合数 以下所有范围都可以当成是以下题目的某个Subtask： 给你 $p$，代表模数。 之后会给你一个 $q$，代表询问次数。 每次询问给定 $n$ 和 $m$，问 $C_n^m \bmod p$ 的值。 下面不给定 $q$ 的范围，因为不重要。 以下全部默认 $n \geq m$。 范围1：$n,m \leq 2000,p \leq 10^9+7$ 先递推预处理，然后直接回答询问即可。 递推式：$C_n^m=C_{n-1}^m+C_{n-1}^{m-1}$。 预处理复杂度：$O(n^2)$ 查询复杂度：$O(1)$ 范围2：$n,m \leq 10^6,p \leq 10^9+7,p\text{ is prime}$ 1 先预处理阶乘，然后直接回答询问即可。 回答询问式：$C_n^m=\dfrac{n!}{m!(n-m)!}$。 为了节省时间复杂度，此处还可以预处理一下阶乘的逆元。 2 预处理复杂度：$O(n)$ 查询复杂度：$O(1)$ 范围3：$n,m \leq 10^6,p \leq 10^9+7$ 1 可以发现，范围2与范围3唯一的不同就是，范围3把质数的条件去掉了。 而把质数的条件后，就没法求逆元了，因为逆元可能不存在。 所以我们考虑换做法。 2 我们考虑把模数做个质因数分解，变成 ${p_1}^{a_1} \times {p_2}^{a_2} \times {p_3}^{a_3} \times \dots \times {p_k}^{a_k}$。 ...

This page is just for test 123 $123$ $$ 123 $$ $x^2$ $\color{green}(\sum a_i) \color{default} 123$ 456 456 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123