泪痕@一语成谶
辗转当作浮生妖,流离惊似尘世鬼
原根与模算术 原根与模算术
摘要 啃课件的时侯遇到的数论题,于是来填坑 阶与原根如果 (a,m)=1,记 x 为最小的正整数使得 . 那么 x 称为 的阶。记为 。 可以把阶理解为模意
2019.06.08
[BZOJ2219] 数论之神 [BZOJ2219] 数论之神
摘要 啃课件的时侯遇到的,先放个题解,至于代码的话先咕着 多组数据( 1. . X 在范围 [0, 2K] 内 的 X 的个数. 即求同余方程 $x^a\equiv b\b
2019.06.08
二维凸包 二维凸包
摘要 二维凸包是计算几何中比较入门的部分 二维凸包的定义对于平面上的若干个点 ,二维凸包指的是一个面积最小的凸多边形,把所有的点包含在内部。这个凸多边形以点集的形式表示。实际上可以理解为用一个橡皮筋包含住所有给定点的
2019.05.06
主定理 主定理
摘要 花个 10 分钟学一学主定理 形式假设有递归关系式 T(n)=aT\left(\frac{n}{b}\right)+f(n)其中 . 为问题规模,而 a 为递归子问题的数量,$\frac{n}
2019.05.05
欧几里德算法专题 欧几里德算法专题
摘要 鉴于初等数论的内容太多,于是单独分出一个欧几里德算法的文章,主要讲欧几里德算法,扩欧和类欧 欧几里得算法即辗转相除法,基于 的原理,用于求解最大公约数的问题 int gcd(
2019.05.01
SCOI2010 幸运数字 SCOI2010 幸运数字
摘要 幸运数字:只包含数字 6 和 8 的那些号码。近似幸运数字:幸运数字的倍数。求 的近似幸运数字的个数。 . 首先想到的就是容斥,考虑预处理所有的近似幸运数字,直接容斥是自
2019.05.01
容斥原理入门 容斥原理入门
摘要 啃论文系列~ 考容斥原理本身的题不多,容斥原理常用于某个算法部分的求值。 2019.6.16 编入精选文章。 入门 某班有 a 歌人擅长唱歌,b 个人擅长画画,c 个人既擅长唱歌也擅长画画,问有多少人至少有一种擅长? 发挥你聪明的大
2019.04.25
集合的整数表示 集合的整数表示
摘要 整理一些集合的小操作 对于大小为 的集合,要求我们表示该集合的任意子集,借助于整数的二进制表示,可以按以下方式编码为整数 f(s)=\sum_{i\in s}2^i位运算借助位运算来进行集合的运算。一系列例子: 意
2019.04.20
[POI2014]HOT-Hotels [POI2014]HOT-Hotels
摘要 题意:一颗无根树,每条边长度相同。选 3 个点两两距离相等,有多少种方案? . 不难证明三条路径交汇于一个中心点。以这个中心点为根的话,那么这三个结点深度相同。于是我们枚举根结点,并统计每一个深度的结点数(注意
2019.04.06
高斯消元 高斯消元
摘要 Gaussian Elimination,一种求解线性方程组的算法 概述高斯消元是一种求解线性方程组的方法。 线性方程组与増广矩阵我们把 \left\{\begin{matrix} a_{1,1}x_1+a_{1,2}x_2+\c
2019.04.04
[BZOJ5372] 神仙的游戏 [BZOJ5372] 神仙的游戏
摘要 一道综合生成函数和多项式乘法的题 这道题提醒我,空间一定要开够!(记得双倍,尤其是计算长度的时候) 题意定义字符串 的 border 是满足以下条件的 : \forall i\in\{1,2
2019.02.15
多项式与多项式乘法 多项式与多项式乘法
摘要 鸽鸽给我们讲课啦 据说讲课前通宵玩了两天。早上灵车漂移。 多项式定义给定一个环 ,( 通常是交换环,可以是有理数、实数或者复数等等)以及一个未知数 x,则任何形同 \sum_{i=0}^na
2019.02.15
筛法自闭 筛法自闭
摘要 tqy 奆奆继续给我们讲数论啦 洲阁筛待更 数论函数与积性函数数论函数,积性函数,完全积性函数的定义、性质 常见数论函数 SPOJ DIVCNT1 \sum_{i=1}^n\sigma(i)\\ =\sum_{i=1}^n\sum_
2019.02.14
概率期望小结 概率期望小结
摘要 Tqy 奆奆给我们讲概率啦 概率与期望概率空间三元组 . 被称为概率空间: 样本空间 是一个非空集合 集合 的元素是 的子集, 是样本空间 $\Omeg
2019.02.13
初探母函数 初探母函数
摘要 本文主要介绍普通母函数及其应用 定义在数学中,某个序列 的母函数(又称生成函数,英语:Generating function)是一种形式幂级数,其每一项的系数可以提供关于这个序列的信
2019.01.26
初等数论小结 初等数论小结
摘要 复习一下数论 符号的说明 大 符号:当且仅当存在正实数 和实数 ,使得 ,我们就可以认为,$f(x)=O(g(x
2019.01.26
SCOI2008 奖励关 SCOI2008 奖励关
题意在奖励关里,系统将依次随机抛出 k 次宝物,每次你都可以选择吃或者不吃。宝物一共有 n 种,第 k 次抛出各个宝物的概率均为 。 获取第 i 种宝物将得到 分( 可以是负数),但第 i 种
2019.01.17
杜教筛 杜教筛
摘要 莫比乌斯反演推完式子后,一般考虑线性筛和数论分块。当要求在低于线性时间的求解积性函数前缀和的问题的时候就会用到杜教筛。 符号说明简单解释一下本文可能用到的记号的含义。 狄利克雷卷积符号 表示数论函数
2019.01.11
莫比乌斯反演小结 莫比乌斯反演小结
摘要 复习莫比乌斯反演~ 前言OI 的数论涉及求和的部分,一般采用 暴力计算;但是当上界过大的时候就需要考虑数论求和法。 常用的技巧有前缀和、差分、组合计数、等差数列求和、矩阵快速幂等,这些技巧都建立在数学原理的基础上 如果
2019.01.10
组合数漫谈 组合数漫谈
排列与组合在考虑一类计数问题的过程中,我们常常会遇到讨论排列或者组合的问题。 排列数从 n 个不同元素中,任取 m 个元素按照一定的顺序排成一列,叫做从 n 个不同元素中取出 m 个元素的一个排列;从 n 个不同元素中取出 m 个元素的所有
2018.12.21
1 / 2