泪痕 @ 铁憨憨
辗转当作浮生妖,流离惊似尘世鬼
斐波那契数列 斐波那契数列
斐波那契数列(The Fibonacci sequence,OEIS A000045)的定义如下: F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}该数列的前几项如下: 0, 1, 1, 2, 3, 5
2019.07.21
Tewelvefold way Tewelvefold way
摘要 今天我们来探讨一道综合计数题。 问题描述 n个有标号/无标号的球分给m个有标号/无标号的盒子,盒子有三种限制: A. 无限制B. 每个盒子至少有一个球C. 每个盒子至多一个球 共12种问题。问方案数。(所有球都要放) 为了方便,将
2019.07.20
扩展埃氏筛 扩展埃氏筛
摘要 本文介绍一种比欧拉筛更高效的筛法,扩展 Eratosthenes 筛法。 杜教筛适用范围较小,未充分利用积性。扩展埃氏筛要求对于任意质数 p, 是一个关于 p 的低阶多项式。对于任意 的指数
2019.07.13
原根与模算术 原根与模算术
摘要 啃课件的时侯遇到的数论题,于是来填坑 阶与原根如果 (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
1 / 2