祝馀宫

文章总览：雪地的圣女计算几何，好像是非常难的一部分……其实还是数学，说着难，其实也还好（好罢我不会）。总而言之，这篇文章来简单介绍一下最最基础的计算几何，下为本文大纲： 向量的定义 向量的运算 直线表示法 直线的运算 凸包的定义 凸包的运算 半平面定义 半平面模板 几何大模板 几何例题一 几何例题二 前置知识：付记忆入殓 向量的定义 向量的运算 定义：悲鸣，赐死之先声首先定义向量，其实向量在以前的文章也接触过，不过比较基础，而且并没有给出详细的定义，所以说我们还是先说一个较为形式化的定义。 友情链接： 【算法介绍】快速傅里叶变换 - 复数及其运算 | 祝馀宫 向量，顾名思义就是有方向的量，在数学上来说，只要不改变向量的大小和方向，其端点是可以随意再平面中移动的，一般记作 $\vec a$ 。事实上，向量可以认为是一个有向的线段，而有向线段的三要素非常相似于力的三要素，即起点、方向、长度。所谓三要素，就是只要知道了这三个信息，剩下的信息就可以唯一确定，所以我们也用有向线段来表示向量。 除此之外，向量还有一些其他的概念。 向量的模长：就是向量的长度，记作 $|a|$； 零向量： ...

文章总览：一心平衡树是我 114514 年前就说要学的知识点，结果拖到现在……甚至这个封面都是今年春节前就做好了qwq。因为我太菜了，这篇文章主要讲的内容是普通的二叉搜索树和两种 Treap（或许封面得改成 Treap 专题？ 下为本文大纲： 二叉搜索树概念简介 二叉搜索树分段推导 二叉搜索树优劣分析 无旋 Treap 基本概念 无旋 Treap 思想模拟 无旋 Treap 区间操作 无旋 Treap 综合例题 带旋 Treap 思想简介 带旋 Treap 分段实现 带旋 Treap 代码一览 两类 Treap 对比分析 前置知识：二观 二叉搜索树概念简介 二叉搜索树分段推导 二叉搜索树优劣分析 概念讲解：幽府说起二叉搜索树，各位并不陌生，在很久很久以前，我曾写过这样一篇文章： 友情链接： 【算法介绍】笛卡尔树 | 祝馀宫 这里面提到的笛卡尔树，也是二叉搜索树的一种。不过那篇文章并没有详细解释二叉搜索树的详细定义与编码方式，所以说作为平衡树重要的前置知识，我们把二叉搜索树一并在这里讲了。 首先我们来简单介绍一下二叉搜索树的概念。 规定每个节点有一个附加权值。 左子树和右子树 ...

文章总览：盐与犬豪德，失踪多年的我终于回来写文章了（什么？你说我干什么了？你怎么知道我出遐蝶了！），，，言归正传，这篇文章的内容是 CDQ 分治，最近做到了一道关于 CDQ 分治的题目，一看就发现不会，所以这篇文章来讲一下 CDQ 分治的一些基本原理与应用，所谓 CDQ 分治，更广泛的来说是一种思想，它在被提出之前就已经广泛流传于各大巨佬之间，后来被高中的 IOI2008 金牌得主陈丹琦总结，因此而得名。 话说这剧情怎么这么熟悉，上次讲莫队的时候好像和这个剧本完全一样 下为本文大纲： 二维数点问题的规律总结 CDQ分治思想的简单推导 CDQ分治模板题讲解 CDQ分治的简单应用 前情回顾：狮子之尾 友情链接： 【算法介绍】二维数点 | 祝馀宫【算法介绍】扫描线思想 | 祝馀宫 上面这两篇是我曾经结下的关于二维数点的一些文章。我们可以简单的总结一下，从最最开始的一维数点，是如何一步一步拓展到二维数点的呢？ 首先来从一维数点讲起，这应该是数点问题的起源。什么是数点？举个例子，现在我有一个一维的数轴，我往上面标点，标了点以后，查询某一区间，或者某一前缀等等等等有多少个点。这就是一维数点问 ...

文章总览：群星岸落之夜如你所见，这篇文章的主题是概率与期望。众所周知，概率与期望早就占领了各大领域，比如说投篮的命中率可以表达一个选手的投篮水准，竞赛题目设置很多测试点来测试代码本质是一种抽样调查，等等等等。但是说概率与期望，在初中或者高中课本中都是占比非常大的部分（刚刚好我也打算顺手学了），所以这篇文章的前半部分注重于一些课本上的基础知识介绍与讲解，后面会浅浅的说一些信竞方面的概率期望。 下为本文大纲： 概率基本知识介绍及计算 全概率公式与贝叶斯公式 期望、方差与线性相关性 二项、超几何及正态分布 期望线性性以及简单运用 随机游走的问题概率模型 概念基础：穿过锁孔之风 样本空间与概率定义 古典概型与概率加乘 独立事件与条件概率 全概率与贝叶斯公式 概率定义：这是魔法哟关于概率的定义，你可能会说：“这玩意不是烂大街了嘛吗？还有人不会的？”正确的，概率的定义其实大家都知道是那个意思，可是实际上从稍微严谨的角度出发的概念以及一些性质可能并不广为人知，我们要学概率，就要从最基础概念开始：概率的基础——事件。 对于一个事件，可以是世间万物，比如说下面几个都可以是事件： 在一个既有青蛙又 ...

文章总览：落井当下石这篇文章讲的内容是斯特林数和卡特兰数，两个非常常用的计数类型数列，初赛常考（好吧我怎么感觉斯特林数我从来没有见到过） 本文内容限定如下： 第一类斯特林数推导及实现 第二类斯特林数推导及实现 斯特林数例题 卡特兰数推导及应用 卡特兰数例题 算法其一：得胜必追击 第一类斯特林数推导及实现 第二类斯特林数推导及实现 第一类斯特林数第一类斯特林数就是：将 $n$ 个不同物体排成 $k$ 个互不区分的非空圆排列的方案数。 可以简单的分来讨论，对于第一类斯特林数 $S1(n,k)$： 对于第 $n$ 个数新开了一个圆排列，方案数为 $S1(n-1,k-1)$。 对于第 $n$ 个数插入了以前某一个圆排列，方案数为 $(n-1)\times S1(n-1,k)$，因为在插入这个数以前，一共有 $n-1$ 个数，由于是圆排列，环上的空位数量还是 $n-1$ 个，所以乘起来。 边界条件也是非常的明显是 dp[0][0]=1 。 123456dp[0][0] = 1;for(int i = 1; i <= n; i++) { for(int j = 1; ...

文章总览：坠临万界的星芒欧拉函数和欧拉定理也是非常基础的数论知识。欧拉函数做为积性函数，并且自身携带欧拉名称加持各种优良性质，被广泛的运用到各个数学推导方面；而欧拉定理更是必不可少，计算逆元是它最基本的运用，它也是凌驾于费马小定理的存在（费马小定理可以从欧拉定理中得出）；并且其拓展即拓展欧拉函数还可以在取模运算中缩小大指数范围，等等等等。接下来我们介绍无所不能的——欧拉函数与欧拉定理。 欧拉函数推导 欧拉函数性质 欧拉函数的计算 欧拉函数拓展 欧拉定理推导 拓展欧拉定理推导 概念基础：因缘假合的人身 欧拉函数推导 欧拉函数性质 欧拉函数基础推导关于欧拉函数，就从最基础的开始讲起。我们定义函数 $\varphi(n)$ 表示从 $1$ 到 $n$ 的数字中与 $n$ 互质的有多少个。这就是欧拉函数所表示的信息。那么关于欧拉函数我们能有什么已知的值吗？ 非常显然的，对于一个质数 $p$，其欧拉函数值 $\varphi(p)=p-1$ 这是显然的，因为 $p$ 作为质数显然与 $1\sim p$ 之间的除了它本身以外任何数字互质。其次有一个容易让人纰漏的点，那就是 $\varphi(1 ...

文章总览：远行雪杖的清晨排列组合，这是初赛题目和复赛数学题目中必不可少的一部分，同时也是大多数计数类 DP 的重难点所在。其特点就是各种题目百出不厌，千变万化，让人措不及防，但是实际上中国有句古话叫做“万变不离其宗”，排列组合的问题也是有一定套路可言的。本篇文章旨在总结大多数类型的排列组合基础模型以及使用方式，排列组合问题计算时几个常见的思考方向，等等等。下为文本大纲： 组合数基础 二项式定理 隔板法基础 组合数例题 排列数基础 错位排列 圆排列 多重集合排列 康托展开 排列组合综合应用 组合基础：便携炉具的正午 组合数基础 二项式定理 隔板法基础 组合数基础推导组合数大家绝对不陌生，组合数指的就是 $n$ 个数里面选出 $m$ 个，不考虑取出的顺序，有几种取法，这个取法的方法数量就是大家常见的 $C_n^m$。 举个最常见的例子，我有 $6$ 个数字，我要从中选出 $3$ 个，那么他表示成刚刚的符号就是 $C_6^3$，但是问题是如何计算呢？非常显然的，如果我们考虑取数的顺序，那么计算出来的就是排列数，我们划去排列即可。 具体的，第一个数字有 $6$ 种取法，第二个数字就少了一 ...

文章总览：穷高极天，亢盈难久中国有句古话：“有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？”上过小学一年级的我们都知道，这是非常经典的同余方程组，而它的解法，就是这篇文章要讲的中国剩余定理 $\tt Chinese\ Remainder\ Theorem$。 本文内容限定于下： 中国剩余定理证明 中国剩余定理实现 拓展中国剩余定理证明 拓展中国剩余定理实现 推导其一：威制八毒，灭却炎烟 同余方程的计算&通解形式 通解形式正确性证明 从实例出发的推导那么从开篇提到的“物不知数”问题出发，我们可以得到下面的同余方程组： \begin{cases} x\equiv 2\pmod 3\\ x\equiv 3\pmod 5\\ x\equiv 2\pmod 7 \end{cases}其实这个题目很早就有了答案，“三人同行七十稀，五树梅花廿一支，七子团圆正半月，除百零五便得知。”这是来自于明朝数学家程大位在《算法统宗》中的解答口诀。其含义即是关于这个问题的通解形式，其中第一个字的表示模数，最后一个词中的数字表示每一个同余方程余数要乘以的系数，最后加起来模 $10 ...