泪痕 @ 铁憨憨
辗转当作浮生妖,流离惊似尘世鬼
杜教筛 杜教筛
摘要 莫比乌斯反演推完式子后,一般考虑线性筛和数论分块。当要求在低于线性时间的求解积性函数前缀和的问题的时候就会用到杜教筛。 符号说明简单解释一下本文可能用到的记号的含义。 狄利克雷卷积符号 表示数论函数
2019.01.11
莫比乌斯反演小结 莫比乌斯反演小结
摘要 复习莫比乌斯反演~ 前言OI 的数论涉及求和的部分,一般采用 暴力计算;但是当上界过大的时候就需要考虑数论求和法。 常用的技巧有前缀和、差分、组合计数、等差数列求和、矩阵快速幂等,这些技巧都建立在数学原理的基础上 如果
2019.01.10
组合数漫谈 组合数漫谈
排列与组合在考虑一类计数问题的过程中,我们常常会遇到讨论排列或者组合的问题。 排列数从 n 个不同元素中,任取 m 个元素按照一定的顺序排成一列,叫做从 n 个不同元素中取出 m 个元素的一个排列;从 n 个不同元素中取出 m 个元素的所有
2018.12.21
卡特兰数 -Catalan 卡特兰数 -Catalan
卡特兰数又称卡塔兰数,英文名 Catalan number,是组合数学中一个常出现在各种计数问题中出现的数列。以比利时的数学家欧仁 · 查理 · 卡塔兰 (1814–1894) 的名字来命名。 计算 \begin{split} &T_0=
2018.12.21
博弈论 博弈论
摘要 博奕论,一门高深的学问。 2019.6.15 编入精选文章。 dls 讲博弈论:“你掉线,我随意” 博弈的分类博弈大体分为平等博弈和不平等博弈。平等博弈指双方的决策集等价,不平等博弈则指双方决策集不等价。 常见的平等博弈则则是 I
2018.12.13
[POJ1845]Sumdiv [POJ1845]Sumdiv
分析对 a 分解质因数: a=\prod_{i=1}^k{p_i}^{c_i}于是 a 的因数和表示为 \sigma_a=\prod_{i=1}^{k}\left(\sum_{j=0}^{c_i}{p_i}^j\right)括号里是一个
2018.11.24
欧拉函数 | 欧拉定理 欧拉函数 | 欧拉定理
摘要 复习一下欧拉定理,顺便打了洛谷新出炉的模板~ 欧拉函数定义欧拉函数用希腊字母 表示, 表示 的欧拉函数。 的值为小于等于 且与 互质的数的
2018.11.16
线性筛 | 欧拉筛 线性筛 | 欧拉筛
线性筛质数每个数被最小的质因子筛一次。 int pn[N],cnt; bool vis[N]; void pri(int n){vis[0]=vis[1]=1; for(int i=1;i<=n;i++){if(!vis[i]
2018.11.16
【笔记】数和序列 【笔记】数和序列
前置知识极端原理每个非空的正整数集合都有一个最小元。 每个非空的负整数集合都有一个最大元。 有理数和无理数如果存在整数 ,使得 ,则称实数 是有理数,否则 是无理数。 取整 &
2018.10.13
矩阵加速 矩阵加速
简介 矩阵加速,用于计算数列的第 n 项(当 n 的数值过大,线性算法超时时)。 这里的数列限指 K 阶常系数线性递推式 原理矩阵快速幂 大致分三步: 将原式化为矩阵 矩阵乘法分离,建立矩阵递推关系 找到起始项,建立常数矩阵幂关系(可用
2018.10.03
矩阵乘法 矩阵乘法
矩阵定义在数学中,矩阵(Matrix)是一个按照长方阵列排列的复数或实数集合,最早来自于方程组的系数及常数所构成的方阵。例如,矩阵 A: A=\begin{bmatrix} a_{1,1} &a_{1,2} &\cdots &a_{1,m
2018.10.03
概率与期望 ·expectation 概率与期望 ·expectation
概率的定义概率, 又称“或然率”、“几率”, 它是对一个随机事件的可能性的大小所作的数量方面的估计。 一个事件 A 出现的概率, 是 A 可能出现的情况与全部可能情况的比率。其计算公式为: P(A)=m(A 可能出现的情况)/n(所有可能的
2018.10.01
2 / 2