线性筛 欧拉筛 线性筛（又称欧拉筛）是一种线性求素数的筛法，可以在 \(O(n)\) 的时间内找出 \(n\) 以内的所有素数。 线性筛的基本思想是，对于 \(i\) 从 \(2\) 到 \(n\) 的每个数，如果它不是素数，则枚举已筛出的每个素数，若其非 \(i\) 的因子，则将 \(i\) 乘上该素数的积标记为已被筛掉。直到枚举到 \(i\) 的最小质因子。这样，当 \(i\)...

懒标记 线段树要做到其 \(O(\log n)\) 的更新和查询，就需要用到懒标记。 懒标记的作用是，当我们对线段树的某些节点（区间）进行更新时，我们并不立即更新这些节点的值，而是将这些更新操作延迟到下一次查询或更新时再进行。 洛谷已经为我们排好了对线段树的逐层深度学习XD P3372 【模板】线段树 1 1234567891011121314151617181920212...

线段树在维护区间时可以维护任何区间信息，比如，一个单调栈。 P4198 楼房重建 题意：维护全局最大上升序列大小。 更新 线段树当前节点存储整个区间的最大值，对于该题，左子树的区间答案可以直接继承，然后用左子树区间的最大值查询右子树的答案并记录在该节点上。 123456void update(const int &x,const double &k,const in...

莫涛大佬的知乎 莫队算法是一种暴力分块的算法，它能够减少移动次数提高效率。 使用需要转化在线算法为离线算法。具体见下方题目的题解。 P2709 小B的询问 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606...

关闭流同步 1std::ios::sync_with_stdio(false); 关闭输入输出流与标准输入输出（scanf printf）的同步，加快流速度，但关闭后不可混用。 整形快读 从标准输入流读入一个 int 12345678#include<cctype>#include<cstdio>inline int read(){ int...

费马小定理 对于任何互质数 \(a,p\),有 \[ a^{p-1}=1\pmod p \] 应用 求逆元： \[ a^{p-2}=a^{-1}\pmod p \]

我知道是伪随机数生成啦 可以用 srand(time(0)) 和 rand() 函数生成伪随机数。然而，这个方法生成的随机数效果不是很好，也没法指定生成范围。 下面的方法可以生成指定范围的随机数。如果修改分布，还可以得到符合特定分布的随机数。 mt19937 c++11 加入。 定义一个名叫 rd 的随机数生成器（括号内为种子）。 12mt19937 rd(std::chron...

前言 该内容算法竞赛涉及不多，属于较深概率论内容。 鞅的停时定理 “鞅”，martingale 用来指一类随机过程，定义如下： 鞅是一种离散时间的随机过程 \(X_0,X_1,\cdots\) 满足： \(E(X_t)<\infty,\forall t\geq0\) \(E(X_{t+1}\mid X_0,\cdots X_t)=X_t\) 根据定义可...

前言 我原在博客园上发表的这篇文章是阅读排行榜最高的一篇。然而，作为一个刚学竞赛的学生写的东西，它的质量实在堪忧。行列式又是一个及其重要、基础和困难的概念，无论对于大学数学还是高中竞赛。因此，我决定将这篇文章重新编辑，以便更好地帮助学习的人。 如果你想知道行列式是什么，强烈建议先去学习线性代数基础知识，了解什么是向量、矩阵、线性变换以及会用矩阵描述线性方程组，然后认真理解学习行列式的概念...

我不知道我看到我没通过审核之后的感觉是怎样的。很复杂。 我感到很不真实。因为明明没有收到电话。我第一反应是搞错了。 但那冷冰冰的文字就在那。我读了一遍又一遍，它就在那。班主任也看到了。他们都看到了。传开了了。 “快让学生查下结果，有个学生没接到电话被拒绝了。” 我感到气愤。因为清华甚至没有前天给我打电话。 我感到失望。因为这落差实在太大了。 我前天还在为其他被拒绝的学生鸣不平。我...